상위 문서: Data Structures
개요
해시 테이블(Hash Table)은 사전(Dictionary)을 구현하는 데에 매우 실용적인 자료 구조이다. 해시 테이블의 근본적인 아이디어는 배열에서 인덱스만 주어지면 이를 바탕으로 원하는 원소에 즉시 접근할 수 있다는 것이다. 이때 키(key)는 보통 정수(integer)가 아니므로, 임의의 키를 정수 인덱스로 바꾸는 해시 함수(hash function)를 구현하고 응용하는 것이 해시 테이블의 골자이다.
Collisions
충돌(Collision)이란 서로 다른 두 키가 동일한 해시 값에 매핑되는 현상이다. 충돌이 발생할 경우에는 해당 버킷 안에 여러 키가 모이게 된다. 이때 키들이 해시 함수에 의해 균등(uniformly)하게 버킷들에 분포된다면, 각 버킷에는 몇 안되는 원소들만 들어간다. 따라서 이 경우에는 각 버킷 내부의 작은 리스트만 탐색하면 되므로 여전히 효율적이다. Figure 1은 해시 테이블의 크기가 10인 자료구조에 키 55, 21, 2, 13, 34, 5, 8, 3 등이 해시 값에 따라 여러 버킷에 들어가 있는 것을 보여준다.
Collision Resolution by Chaining
Chaining은 충돌이 발생하였을 때 이를 해결하는 방법중 하나로, 각 버킷마다 연결 리스트(linked list)를 두어 충돌이 발생할 때마다 새 원소를 해당 버킷의 리스트에 추가하는 방식이다. 이는 구현이 단순하고 직관적이라는 장점이 존재하지만, 각 리스트가 포인터를 필요로 하므로 메모리 낭비가 발생한다는 단점이 있다.[1] Figure 1은 Chaining의 한 예시로, 버킷에 해당하는 키 값들이 포인터를 통해 연결되어 있다.
시간 복잡도는 삽입/삭제/탐색 연산이 모두 리스트에서 처리되므로 리스트 길이에 비례한다. 이때 리스트의 길이는 평균적으로 [math]\displaystyle{ n/m }[/math][2]이므로 따라서 시간복잡도는 [math]\displaystyle{ O(n/m) }[/math]이다. 이때 [math]\displaystyle{ n/m }[/math]은 적재율(load factor)라고 불린다.
Open Addressing
Open addressing은 체이닝 대신 포인터를 쓰지 않고, 테이블 내부에서 다른 빈 공간을 찾아 저장하는 방식이다. 해당 방식은 원래의 해시 값이 가리키는 칸이 비어 있으면 삽입하고, 이미 차 있으면 다음 위치에 삽입하는 것을 시도하는 방식이다. 이때 충돌할 경우 다음 위치를 정하는 규칙은 아래와 같다:
- Sequentially: h,h+1,h+2,...
- Quadratically: h, h+12, h+22, h+32, ...
- Linearly: h, h+k, h+2k, h+3k, ...
Figure 2는 linear probing 방식의 한 예시를 보여준다. 해당 방식은 별도의 포인터 저장이 불필요하다는 장점이 있지만, 원소들이 뭉쳐서 연속 구간을 차지하면(Primary Clustering) 탐색 성능이 저하된다는 단점이 있다. 또한 해당 방식은 원소를 삭제할 때 어려움을 겪는데, 이는 원소를 삭제할 때 단순히 해당 칸을 비워버리면 문제가 생기기 때문이다. 왜냐하면 삭제 이후 탐색 시 “그 원소가 충돌 때문에 다른 칸에 있는지” 구분이 불가능해져서[3], 일부 원소가 검색 불가능해지기 때문이다. 따라서 보통은 “삭제된 자리”를 특별한 마커(예: DELETED flag)로 표시해 해결한다.
Hash Functions
해시 함수(Hash function)의 가장 중요한 역할은 키(key) 를 정수(integer) 로 변환하는 것이다. 예를 들면 키가 "apple"일 때, 이를 어떤 정수값으로 바꾸는 것이다. 이때 좋은 해시 함수의 조건은 아래와 같다:
- 계산이 저렴해야 함(Is cheap to evaluate)
해시 함수가 복잡하면 해시 테이블을 쓰는 의미가 없으므로, 빠르고 단순하게 변환해야 한다. - 모든 해시 테이블 슬롯을 고르게 사용(Tends to use all positions from 0 … M uniformly)
해시 테이블의 크기가 M이라면, 해시 함수의 결과로 인덱스 0부터 M-1까지 고르게 값이 나와야 충돌(collisions)이 줄어든다.
아래는 문자열 키를 정수로 바꾸는 어떤 해시 함수이다:
[math]\displaystyle{ h=\sum^{Key\,Length}_{i=0}128^i\times char(key[i]) }[/math]
위와 같은 해시 함수의 결과로는 매우 큰 정수가 나올 수 있다. 만약 해시 함수의 결과가 1,928,374,982 같은 수라면, 해시 테이블 크기보다 훨씬 클 수 있다. 따라서 해당 결과를 테이블 크기에 맞게 줄이는 작업을 해야 한다. 이는 아래와 같은 방법을 사용한다.
[math]\displaystyle{ h(k) = k\, mod\, M }[/math]
위에서 k는 해시 함수를 통해 1차적으로 얻은 큰 정수를 의미하며, M은 해시 테이블의 크기를 의미하며, 모듈러 연산을 통해 결과값이 항상 0~k-1 범위 내에 있도록 한다. 이때 M의 값은 2i-1[4]에 너무 가깝지 않은 M은 큰 소수로 선택하는 것이 권장된다. 만약 M을 2의 거듭제곱수로 사용한다면, k를 이진수로 바꾸었을 때 하위 비트만을 이용하므로 충돌이 증가한다. 또한 M이 소수가 아니라면, 키 값이 특정 배수 패턴을 가질 때 특정 버킷들에 모이므로 충돌이 늘어난다.
예를 들어, 사회보장번호(SSN)의 앞 세 자리를 해시 키로 쓰는 경우는 나쁜 해시 함수이다. 그 이유는 사회보장번호 앞 세 자리는 지역이나 특정 규칙에 따라 배정되므로 값이 편향되어 있기 때문이다.[5] 하지만 SSN의 뒷 세 자리를 해시 키로 쓰는 경우는 좋은데, 마지막 세 자리는 지역과 상관없이 거의 무작위(random)로 배정되므로 훨씬 균일한 분포를 보이기 때문이다.
The Birthday Paradox
아무리 좋은 해시 함수를 사용하더라도 충돌은 피하기 힘들다. 그 이유는 birthday paradox 때문인데, 이는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50% 이상이 된다는 것이다. 이는 삽입할 때마다 충돌 확률은 누적되어 올라가기 때문이다. 해시 테이블의 크기가 m일 때 n개의 키를 삽입하면 아래와 같은 충돌 확률을 가진다:
[math]\displaystyle{ P(no collision) = \frac{m}{m} \times \frac{m-1}{m} \times \frac{m-2}{m} \times \cdots \times \frac{m-n+1}{m} = \prod^{n-1}_{i=0}\frac{m-i}{m} }[/math]
Applications of Hashing
Performance on Set Operations
해시 테이블을 이용한 딕셔너리 연산들의 성능을 분석하면 아래와 같다:
- Search (탐색)
기대 성능(Expected): O(1) [math]\displaystyle{ \rightarrow }[/math] 해시 함수가 키를 고르게 분산한다면 평균적으로 한 번에 원하는 원소를 찾을 수 있음.
최악의 경우(Worst case): O(n) [math]\displaystyle{ \rightarrow }[/math] 모든 원소가 같은 버킷에 몰려 linked list처럼 되면 전체를 다 탐색해야 함 - Insert (삽입)
기대 성능(Expected): O(1) [math]\displaystyle{ \rightarrow }[/math] 해시 함수 계산 후 그 자리에 넣기만 하면 됨.
최악의 경우(Worst case): O(n) [math]\displaystyle{ \rightarrow }[/math] 충돌이 많이 나서 특정 버킷에 길게 쌓이면 삽입도 느려짐. - Delete (삭제)
기대 성능(Expected): O(1) [math]\displaystyle{ \rightarrow }[/math] 원소를 찾고 삭제하면 끝.
최악의 경우(Worst case): O(n) - Min / Max / Predecessor / Successor: [math]\displaystyle{ \Theta(n+m) }[/math] [math]\displaystyle{ \rightarrow }[/math] 해시 테이블은 정렬 구조가 아니기 때문에 최솟값/최댓값이나 이전/다음 원소 같은 연산은 효율적으로 할 수 없기 때문.
정리하자면, 해시 테이블은 탐색/삽입/삭제 연산에 평균적으로 매우 빠른 시간 복잡도를 제공한다. 하지만 최악의 경우 시간 복잡도는 선형적으로 늘어나기 때문에, 성능은 예측 불가능하다고 말할 수 있다. 따라서 보다 안정적인 성능의 연산을 사용하고자 할 때에는 균형 이진 탐색 트리(Balanced Binary Search Tree)가 더욱 낮다.