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}$

Applications of Hashing

Performance on Set Operations

해시 테이블을 이용한 딕셔너리 연산들의 성능을 분석하면 아래와 같다:

• Search (탐색)
  기대 성능(Expected): O(1) $\to$ 해시 함수가 키를 고르게 분산한다면 평균적으로 한 번에 원하는 원소를 찾을 수 있음.
  최악의 경우(Worst case): O(n) $\to$ 모든 원소가 같은 버킷에 몰려 linked list처럼 되면 전체를 다 탐색해야 함
• Insert (삽입)
  기대 성능(Expected): O(1) $\to$ 해시 함수 계산 후 그 자리에 넣기만 하면 됨.
  최악의 경우(Worst case): O(n) $\to$ 충돌이 많이 나서 특정 버킷에 길게 쌓이면 삽입도 느려짐.
• Delete (삭제)
  기대 성능(Expected): O(1) $\to$ 원소를 찾고 삭제하면 끝.
  최악의 경우(Worst case): O(n)
• Min / Max / Predecessor / Successor: $\mathrm{\Theta }(n+m)$ $\to$ 해시 테이블은 정렬 구조가 아니기 때문에 최솟값/최댓값이나 이전/다음 원소 같은 연산은 효율적으로 할 수 없기 때문.

정리하자면, 해시 테이블은 탐색/삽입/삭제 연산에 평균적으로 매우 빠른 시간 복잡도를 제공한다. 하지만 최악의 경우 시간 복잡도는 선형적으로 늘어나기 때문에, 성능은 예측 불가능하다고 말할 수 있다. 따라서 보다 안정적인 성능의 연산을 사용하고자 할 때에는 균형 이진 탐색 트리(Balanced Binary Search Tree)가 더욱 낮다.

Hashing in Managing Big Files/Data

Google의 Udi Manber는 "구글의 세 가지 중요한 알고리즘은 hashing, hashing, hashing"이라고 말한 적이 있다. 이는 해싱이 검색과 데이터 처리에서 매우 큰 역할을 한다는 것을 알려준다. 이는 해싱이 큰 데이터를 짧고 독특한 해시 코드로 표현할 수 있다는 특징 때문이다. 이러한 해싱의 특징은 문서 유서도를 판별하거나 표절을 감지하는데에도 사용된다. 새 문서를 해시하여 기존 문서들의 해시와 비교했을 때 같은 해시 값이 존재한다면 중복 문서로 판단하는 것이다. 또한 문서를 여러 겹치는 구간(window)로 나누어 해시를 하고, 이를 비교하는데 사용하여 해시 충돌이 있다면 표절로 볼 수 있다.

Integrity Checking

파일이 변조되지 않았음을 확인하는 방법으로는 암호학적 해시(cryptographic hash)가 있다. 이는 어떤 파일의 해시를 처음 계산해 기록해 둔 후, 나중에 다시 해시를 계산했을 때 값이 동일하면 파일이 변하지 않은 것이다. 단 1바이트라도 바뀌면 해시 값이 완전히 달라진다. 이는 소프트웨어 배포 시 SHA-256 해시를 제공하여 다운로드 받은 파일의 해시를 비교해 변조 여부 확인하는 방식으로 활용된다.

Hashing as a Representation

목적에 맞게 디자인된 해싱 함수(Custom-designed Hashing)는 원소들을 버킷에 표준화된 표현(cannonical representation)으로 저장하는데 사용될 수 있다. 예를 들면, "skiena"와 같은 단어를 알파벳 순으로 정렬하면 "aeikns"가 되는데, 이러한 해싱은 같은 글자들로 이뤄진 단어들을 같은 해시 버킷에 모으는데 활용될 수 있다. 이 역시 예를 들자면 "dog"와 "god"는 같은 문자로 이루어져 있으므로, "dgo"를 의미하는 버킷에 담긴다. 이러한 방식은 비슷한 것끼리 같은 버킷에 모으는 proximity-preserving hashing이라고 한다.