10. 해시테이블 (Hash Table)

해시테이블은 키-주소 매핑에 의해 구현된 사전 ADT의 일종이다.
해시테이블은 버켓 배열과 해시함수로 구성되는데, 각 항목들의 키를 주소로 매핑하여, 1차원 배열에 사전의 원소들을 저장한다.

탐색과 삽입, 삭제에 $O(1)$의 기대시간과 $O(n)$의 최악시간을 갖는다.

버켓 배열

해시테이블을 위한 버켓 배열^{Bucket Array}은 크기 $M$의 배열 $A$로, $A$의 각 원소를 버켓(키-원소 쌍을 담는 양동이)로 본다.

키 $k$를 갖는 원소 $e$는 버켓 $A[k]$에 삽입되는데, 사전에 존재하지 않는 키에 속하는 버켓들에는 NoSuchKey라는 특별 개체를 담아둔다.

키가 유일한 정수이며, $[0,M-1]$범위에 잘 분포되어 있다면 $O(1)$시간을 기대할 수 있는 좋은 방법이지만, 버켓 배열에는 두 가지 중대한 결함이 있다.

그러므로, 해시테이블 ADT를 정의할 때는, 키를 $[0, M-1]$ 범위 내의 정수로 매핑하는 좋은 방식을 함께 사용할 필요가 있다.

해시 함수는 주어진 형의 키를 범위 $[0,M-1]$의 정수로 매핑하는 함수이다. 이 함수 $h$로 매핑된 키 $x$의 값을 $h(x)$, 해시값^{Hash Value}이라 한다.

해시테이블은 해시 함수 $h$와, 크기 $M$의 배열인 테이블로 구성된다.

해시 함수는 보통 두가지 부함수로 구성된다.
키값을 정수로 변환하는 해시코드맵^{Hash Code Map} $h_1$과, 정수를 $[0,M-1]$ 범위에 속하는 정수로 변환하는 압축맵^{Compression Map} $h_2$이다.

좋은 해시 함수는 아래 요소를 갖는다.

메모리 주소^{Memory Adress}
- 키값의 메모리 주소를 정수로 재해석
- 일반적으로 만족스러우나, 동일한 키값이 여럿 존재하는 수치나 문자열에는 적용하기 곤란하다.
정수 캐스트^{Integer Cast}
- 키값의 비트값을 정수로 재해석
- 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에는 적절하다.
요소합^{Component Sum}
- 키의 비트들을 고정길이(16 혹은 32비트 등)로 분할한 후, 각 요소를 합한다. (오버플로는 무시한다.)
- 정수 캐스트와 비슷하나, 정수형의 비트 수를 초과하는 키값에도 사용 가능하다.
- 문자의 순서가 중요한 문자열 키에는 부적절하다.
  - abcd-bcda-cdab-badc... 이들은 모두 같은 요소합을 갖는다.
다항 누적^{Polynomial Accumulation}
- 요소합과 마찬가지로, 키의 비트들을 고정길이로 분할한다.
- 고정값 $z$를 사용하여, 각 요소의 위치에 따른 별도 계산을 부과한 다항식 $p(z)$를 계산한다. (오버플로는 무시한다.)
  $$p(z) = a_0 + a_1z + a_2z^2 + \cdots + a_{n-1}z^{n-1} $$
- 문자열에 특히 적절함.
  ($z=33$일 경우, 50000개의 영단어에서 단 6회의 충돌 발생

압축맵은 해시코드맵을 통해 정수가 된 키값을 우리가 원하는 메모리 범위의 정수로 바꾸는 과정이다.

나누기^division
- $h_2(k) = |k| \% M $
- $M$은 해시테이블의 크기로, 일반적으로 소수를 선택한다.
승합제^{Multiply, add and divide: MAD}
- $h_2(k) = |ak + b| \% M $
- $a$와 $b$는 음이 아닌 정수로서 $a\%M \neq 0$이다. 그렇지 않으면 모든 정수가 동일한 값 $b$로 매핑된다.