Hash Function (해시 함수)
해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.
해시 함수를 수행하기 전의 원래의 데이터를 키 (key), 해시 함수를 수행한 결과값을 해시 값 (hash value)라고 합니다. 그리고 이렇게 키를 해시 값으로 매핑하는 전체적인 과정을 해싱 (Hashing)이라고 합니다.
해시함수는 기본적으로 각각의 키에 대해 모두 다른 해시값을 가집니다. 만약 다른 키에 대래 해시값이 중복된다면, 이를 해시 충돌(Collision)이라고 합니다.
Collision (해시 충돌)
위의 그림은 해싱 과정 중 해시충돌이 발생되는 예시입니다.
해시충돌(collision)은 서로 다른 두 개의 키가 같은 해시값을 가질 때 나타납니다. 위의 그림에서는 John Smith와 Sandra Dee의 해시값이 모두 02로 겹치기에 해시 충돌이 일어납니다. 이러한 해시충돌은 해시함수의 효율성을 떨어뜨리므로, 최대한 일어나지 않게 만드는 것이 중요합니다.
하지만 해시 함수가 무한한 입력값을 받아 해시값을 도출해내는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재합니다.
시간복잡도
- collision 없는 경우:
Big-O(1)- collision 많은 경우:
Big-O(N)
Hash Function의 특징
- 키에 상관없이 항상 고정된 길이의 해시값을 출력한다.
- 눈사태효과
입력 값의 아주 조금만 변경되어도 해시값은 전혀 다른 값이 반환된다.
일반적으로 해시 함수는 키의 일부분을 참조하여 해시값을 만드는 것이 아닌, 키 전체를 참조해서 해시 값을 만들어내기 때문이다. - 해시값으로 키를 유추할 수 없다.
- 같은 키에 대해 항상 같은 해시값을 반환한다.
- 키에 대해 해시값이 항상 1:1인 경우인 함수도 마냥 좋지만은 않다.
항상 1:1 대응이 되도록 만드는 것이 거의 불가능하지만, 만들어도 그것은 array와 다를 것이 없고 메모리도 너무 많이 차지한다. 따라서 hash를 hash답게 사용하지 못하는 경우가 될 수 있다.
이것보다 해시 충돌을 최소화하는 방향으로 설계하고, 해시 충돌에 대비해 대응하는 방법을 만드는 것이 더 중요하다.
Hash Algorithm (해시 알고리즘)
해시 알고리즘은 해시 함수에서 사용되는 알고리즘을 뜻합니다. 해시 알고리즘에 따라 해시 함수의 성능이 좌우됩니다.
해시 알고리즘에는 크게 MD(Message-Direct) Algorithm과 SHA(Secure Hash) Algorithm이 있습니다.
MD5
- 임의의 길이의 입력을 받아서 128비트 길이의 해시값을 출력하는 알고리즘이다.
- MD5는 단방향 암호화이기 때문에 출력값에서 입력값을 복원할 수 없다. 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 적다.
- 패스워드 암호화에서 많이 사용되고, 패스워드를 MD5로 해시해서 나온 값을 저장한다.
- 현재는 MD5 알고리즘을 보안 관련 용도로 쓰는 것을 권장하지 않으며, 심각한 보안 문제를 야기할 수 있다.
SHA
- 1993년부터 미국 NSA가 제작하고 미국 국립표준기술연고수(NIST)에서 표준으로 채택한 해시함이다.
- 1992년 SHA-0의 표준으로 정의되어 발표되었으나, 바로 위험성이 발견되어 이를 보완한 SHA-1이 발표되고 널리 사용되었다.
SHA-0와 SHA-1은 160비트 해시 값을 사용한다.
SHA-1 역시 해시 충돌을 이용한 위험성이 발견되어 차세대 버전으로 넘어가고 있다. - 2001년에 SHA-1에서 개선한 버전인 SHA-2이 발표되었다. 해시 길이에 따라 SHA-225, SHA-256, SHA-384, SHA-512를 선택하여 사용할 수 있으며, 당연히 해시 길이가 길수록 안전하다.
- 2012년 10월에 더욱 안정성이 높은 방식으로 설계된 SHA-3이 정식 발표되었다.
Hash Table (해시 테이블)
해시 테이블이란, 해시함수를 하용하여 키를 해시값으로 매핑하고, 이 해시값을 index 또는 주소로 삼아 데이터의 값(value)을 저장하는 자료구조를 뜻합니다. 이때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬릇(slot)이라고 합니다.
해시 테이블의 기본 연산은 삽입, 삭제, 탐색(search)입니다.
위의 그림은 해시 테이블의 예시입니다. 위의 예시 그림의 버킷에는 데이터가 아래와 같이 저장됩니다.
| Index (Hash Value) | Data |
|---|---|
| 01 | (Lisa Smith, 521-8876) |
| 02 | (John Smith, 521-1234) |
| ... | ... |
해시 테이블의 장점
적은 리소스로 많은 데이터를 효율적으로 관리가 가능합니다.
해시 테이블에서는 1개의 키에 대해 1개의 버킷을 가지고, 버킷의 위치(index)를 키의 해시값으로 가집니다.
해시함수는 동일한 키에 대해 항상 동일한 해시값을 반환하고, 이러한 해시값을 도출해내는 데에는 오랜 시간이 걸리지 않습니다(상수 시간). 해시 테이블은 이런 해시값을 index로 사용함으로써 모든 데이터를 탐색하지 않고 index를 통해 데이터에 바로 접근할 수 있습니다. 이를 통해 해시 테이블을 사용하면 빠른 검색 속도를 가질 수 있습니다. 또한, 해시 테이블에서는 1개의 키를 통해 1개의 버킷에만 접근이 가능합니다.
따라서 적은 리소스로 많은 데이터를 효율적으로 관리가 가능합니다.
해시 테이블을 average case에 대해서 데이터 접근(삽입, 삭제, 탐색) 시 Big-O(1)의 시간복잡도를 갖습니다.
모든 경우에 대한 것이 아니라 average case에 대해 Big-O(1)인 이유는 해시충돌 때문입니다.
Resolve Collision
해시 충돌을 해결하기 위한 방법은 여러가지가 존재합니다.
하지만 모두 기본적인 방법 2가지에서 파생되었기에 여기서는 기본적인 방법 2가지만 알아보려 합니다.
Open Address 방식 (개방주소 방식, 공개주소 방식)
해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식입니다. 버킷이란 바구나와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 됩니다.
이 알고리즘은 Collision이 발생하면 데이터를 저장할 장소를 찾는데, 이 장소를 찾는 방법은 아래의 3가지가 았습니다.
Linear Probing (선형 조사)
가장 간단한 방법입니다. 최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면, 해당 해시값에서 고정 폭(ex. 1칸)만큼 옮겨가면서 다음 해시값에 해당하는 버킷에 데이터가 있는지 확인하는 방법입니다. 다음 버킷에도 데이터가 있다면 계속 반복하고, 데이터가 없는 버킷을 찾는다면 해당 버킷에 저장합니다.
선형 조사는 이동 폭이 지정되어 있기 때문에 특정 해시값 주변 버킷이 모두 채워져 있는 Primary Clusting 문제에 취약합니다. 위의 그림에서 52~56까지 데이터가 저장되어 있고, 임의의 키의 해시값이 52라면 조사를 4번을 수행하고 5번째 수행 때 원하는 위치를 찾을 수 있습니다. 모두 53이 비어있었다면 바로 원하는 위치를 찾을 수 있었겠지만, 이와 같은 경우에는 조사를 많이 해야 한다는 단점이 있습니다.
Quadratic Probing (제곱 조사)
선형 조사가 고정폭만큼 이동하며 조사한다면, 제곱 조사는 이동 폭이 제곱수로 늘어난다는 특징이 있습니다.
예를 들어 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면, 12칸을 이동합니다. 이동한 이후에도 충돌이 일어난다면(버킷이 비어있지 않다면) 이번에는 22칸, 그 다음에는 32칸을 이동하는 식으로 계속 이동 폭을 늘려갑니다.
제곱 조사는 선형 조사처럼 버킷이 몰려있는 경우는 모면할 수 있지만, 여러 개의 다른 키들이 모두 동일한 초기 해시값(이동하기 전의 해시값)을 갖고 있는 Secondaray Clustering에 취약합니다. 초기 해시값이 같다면 다음으로 이동하여 액세스하는 위치 또한 모두 동일하기 때문에 효율성이 떨어질 수 밖에 없습니다.
위의 그림을 예로 들면, 초기 해시값이 7인 데이터를 삽입해야 하는 경우에 선형 조사 기법보다 이동 폭은 크지만, 4번이상 이동 후에 데이터를 저장할 수 있습니다.
Double Hashing (이중 해싱)
이중 해싱은 조사항 해시값의 규칙성을 없애서 clustering(군집화, 저장되는 데이터가 한 곳에 몰리는 문제)를 방지하는 기법입니다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 이동폭을 얻기 위해 사용합니다.
이렇게 되면 최초 해시값이 같은 경우가 많더라도 이동폭이 달라지고, 이동폭이 같더라도 최초 해시값이 달라져 Primary Clusting, Secondaray Clustering 모두 완화할 수 있습니다.
예를 들어,
- 함수
h1: 3으로 나눈 나머지. 해시값 반환. - 함수
h2: 5로 나눈 나머지. 조사 이동폭 결정.
라는 해시함수가 있을 때,
키가 3, 6인 데이터는 모두 최초 해시값은 0이 됩니다. 하지만 키가 3인 데이터의 이동폭은 3, 키가 6인 데이터의 이동폭은 1이 됩니다.
반대로 키가 6, 11인 데이터의 이동폭은 모두 1입니다. 하지만 키가 6인 데이터의 최초 해시값은 0, 키가 11인 데이터의 최초 해시값은 2로 둘의 최초 해시값이 다릅니다.
Separate Chaining 방식 (분리 연결법)
일반적으로 Open Addressing 방식은 Separate Chaining 방식보다 느리다. Open Addressing의 경우, 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문이다. 반면, Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정한다면 Worst Case의 빈도를 줄일 수 있다. Java 7 에서는 Sepatate Chaining 방식을 사용하여 HashMap을 구현하고 있다.
보조 해시 함수 (Supplement Hash Function)
보조 해시 함수의 목적은 키(Key)의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다.
Separate Chaining 방식은 두 가지의 구현 방식이 존재한다.
- 연결 리스트를 사용하는 방식 (Linked List)
- 각각의 버킷들을 연결리스트로 만들어 collition이 발생하면 해당 버킷의 리스트에 추가하는 방식이다.
- 연결리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다.
- 연결리스트의 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다.
- 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.
- Tree를 사용하는 방식 (Red-Black Tree)
- 기본적인 알고리즘은 Separate Chaining 방식과 동일하며, 연결 리스트 대신 트리를 사용하는 방식이다.
- 연결 리스트를 사용할 것인지 트리를 사용할 것인지에 대한 기준은 하나의 해시 버킷에 할당된
Key-Value쌍의 개수로 판단한다. - 데이터의 개수가 적다면 연결리스트를 사용하는 것이 유리하다.
데이터의 개수가 적을 때 Worst Case를 살펴보면 트리와 연결 리스트의 성능이 별 차이가 없다. 하지만 트리는 기본적으로 메모리 사용량이 많기 때문에 메모리 측면에서 봤을 때 데이터가 적을 때는 연결 리스트를 사용한다.데이터가 적다는 것의 기준?
기준은 버킷에 할당된Key-Value쌍의 개수이고, 6개, 8개를 기준으로 한다. 기준이 2개이고 7이 없는 이유는 7 하나만을 기준을 잡게되면 6-7에서 자주 바뀌는 경우에는 매번 연결 리스트와 트리의 구조로 변경해야 하기 때문에 이것이 더 비효율적이기 때문이다. 따라서 조금의 여유를 준 것이다.
Open Address vs Separate Chaining
두 방식 모두 Worst Case의 시간복잡도는 O(M)이다. 하지만 Open Address 방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다.
- Open Address
- 데이터의 개수가 충분히 적을 때 사용한다.
- 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높기 때문이다.
- Separate Chaining
- 위의 경우를 제외하고 사용한다.
- 테이블의 확장을 Open Address 방식보다 줄일 수 있다.
Open Address 방식은 버킷을 계속해서 사용하기 때문이다.
해시 버킷 동적 확장 (Resize)
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 Key-Value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
해시 버킷의 크기를 두 배로 확장하는 임계점은 현재 데이터의 개수가 해시 버킷의 개수의 75%가 될 때이다.
0.75라는 숫자는 load factor라고 불린다.
참고
한재엽님 Github Interview_Question_for_Beginner
gyoogle님 Github tech-interview-for-developer
https://ko.wikipedia.org/wiki/해시_함수
https://siyoon210.tistory.com/85
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
https://yjshin.tistory.com/entry/암호학-해시-함수-작성-중
https://d2.naver.com/helloworld/831311
