Hash Table

상위 문서: Data Structures

개요

해시 테이블(Hash Table)은 사전(Dictionary)을 구현하는 데에 매우 실용적인 자료 구조이다. 해시 테이블의 근본적인 아이디어는 배열에서 인덱스만 주어지면 이를 바탕으로 원하는 원소에 즉시 접근할 수 있다는 것이다. 이때 키(key)는 보통 정수(integer)가 아니므로, 임의의 키를 정수 인덱스로 바꾸는 해시 함수(hash function)를 구현하고 응용하는 것이 해시 테이블의 골자이다.

Collisions

Figure 1. Chaining Hash Table

충돌(Collision)이란 서로 다른 두 키가 동일한 해시 값에 매핑되는 현상이다. 충돌이 발생할 경우에는 해당 버킷 안에 여러 키가 모이게 된다. 이때 키들이 해시 함수에 의해 균등(uniformly)하게 버킷들에 분포된다면, 각 버킷에는 몇 안되는 원소들만 들어간다. 따라서 이 경우에는 각 버킷 내부의 작은 리스트만 탐색하면 되므로 여전히 효율적이다. Figure 1은 해시 테이블의 크기가 10인 자료구조에 키 55, 21, 2, 13, 34, 5, 8, 3 등이 해시 값에 따라 여러 버킷에 들어가 있는 것을 보여준다.

Collision Resolution by Chaining

Chaining은 충돌이 발생하였을 때 이를 해결하는 방법중 하나로, 각 버킷마다 연결 리스트(linked list)를 두어 충돌이 발생할 때마다 새 원소를 해당 버킷의 리스트에 추가하는 방식이다. 이는 구현이 단순하고 직관적이라는 장점이 존재하지만, 각 리스트가 포인터를 필요로 하므로 메모리 낭비가 발생한다는 단점이 있다. Figure 1은 Chaining의 한 예시로, 버킷에 해당하는 키 값들이 포인터를 통해 연결되어 있다.

시간 복잡도는 삽입/삭제/탐색 연산이 모두 리스트에서 처리되므로 리스트 길이에 비례한다. 이때 리스트의 길이는 평균적으로 $n/m$이므로 따라서 시간복잡도는 $O(n/m)$이다. 이때 $n/m$은 적재율(load factor)라고 불린다.

Open Addressing

Figure 2. Sequential Open Address

Open addressing은 체이닝 대신 포인터를 쓰지 않고, 테이블 내부에서 다른 빈 공간을 찾아 저장하는 방식이다. 해당 방식은 원래의 해시 값이 가리키는 칸이 비어 있으면 삽입하고, 이미 차 있으면 다음 위치에 삽입하는 것을 시도하는 방식이다. 이때 충돌할 경우 다음 위치를 정하는 규칙은 아래와 같다:

• Sequentially: h,h+1,h+2,...
• Quadratically: h, h+1², h+2², h+3², ...
• Linearly: h, h+k, h+2k, h+3k, ...

Figure 2는 linear probing 방식의 한 예시를 보여준다. 해당 방식은 별도의 포인터 저장이 불필요하다는 장점이 있지만, 원소들이 뭉쳐서 연속 구간을 차지하면(Primary Clustering) 탐색 성능이 저하된다는 단점이 있다. 또한 해당 방식은 원소를 삭제할 때 어려움을 겪는데, 이는 원소를 삭제할 때 단순히 해당 칸을 비워버리면 문제가 생기기 때문이다. 왜냐하면 삭제 이후 탐색 시 “그 원소가 충돌 때문에 다른 칸에 있는지” 구분이 불가능해져서, 일부 원소가 검색 불가능해지기 때문이다. 따라서 보통은 “삭제된 자리”를 특별한 마커(예: DELETED flag)로 표시해 해결한다.

Hash Functions

해시 함수(Hash function)의 가장 중요한 역할은 키(key) 를 정수(integer) 로 변환하는 것이다. 예를 들면 키가 "apple"일 때, 이를 어떤 정수값으로 바꾸는 것이다. 이때 좋은 해시 함수의 조건은 아래와 같다:

1. 계산이 저렴해야 함(Is cheap to evaluate)
   해시 함수가 복잡하면 해시 테이블을 쓰는 의미가 없으므로, 빠르고 단순하게 변환해야 한다.
2. 모든 해시 테이블 슬롯을 고르게 사용(Tends to use all positions from 0 … M uniformly)
   해시 테이블의 크기가 M이라면, 해시 함수의 결과로 인덱스 0부터 M-1까지 고르게 값이 나와야 충돌(collisions)이 줄어든다.

아래는 문자열 키를 정수로 바꾸는 어떤 해시 함수이다:

$h=\sum _{i=0}^{KeyLength}128^i\times char(key[i])$

위와 같은 해시 함수의 결과로는 매우 큰 정수가 나올 수 있다. 만약 해시 함수의 결과가 1,928,374,982 같은 수라면, 해시 테이블 크기보다 훨씬 클 수 있다. 따라서 해당 결과를 테이블 크기에 맞게 줄이는 작업을 해야 한다. 이는 아래와 같은 방법을 사용한다.

$h(k)=kmodM$

위에서 k는 해시 함수를 통해 1차적으로 얻은 큰 정수를 의미하며, M은 해시 테이블의 크기를 의미하며, 모듈러 연산을 통해 결과값이 항상 0~k-1 범위 내에 있도록 한다. 이때 M의 값은 2ⁱ-1에 너무 가깝지 않은 M은 큰 소수로 선택하는 것이 권장된다. 만약 M을 2의 거듭제곱수로 사용한다면, k를 이진수로 바꾸었을 때 하위 비트만을 이용하므로 충돌이 증가한다. 또한 M이 소수가 아니라면, 키 값이 특정 배수 패턴을 가질 때 특정 버킷들에 모이므로 충돌이 늘어난다.

예를 들어, 사회보장번호(SSN)의 앞 세 자리를 해시 키로 쓰는 경우는 나쁜 해시 함수이다. 그 이유는 사회보장번호 앞 세 자리는 지역이나 특정 규칙에 따라 배정되므로 값이 편향되어 있기 때문이다. 하지만 SSN의 뒷 세 자리를 해시 키로 쓰는 경우는 좋은데, 마지막 세 자리는 지역과 상관없이 거의 무작위(random)로 배정되므로 훨씬 균일한 분포를 보이기 때문이다.

The Birthday Paradox

아무리 좋은 해시 함수를 사용하더라도 충돌은 피하기 힘들다. 그 이유는 birthday paradox 때문인데, 이는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50% 이상이 된다는 것이다. 이는 삽입할 때마다 충돌 확률은 누적되어 올라가기 때문이다. 해시 테이블의 크기가 m일 때 n개의 키를 삽입하면 아래와 같은 충돌 확률을 가진다:

$P(nocollision)=\frac{m}{m}\times \frac{m-1}{m}\times \frac{m-2}{m}\times \cdots \times \frac{m-n+1}{m}=\prod _{i=0}^{n-1}\frac{m-i}{m}$