1. 해시 테이블 (Hash Table)

• 원소가 저장될 자리가 원소의 값 (키 key)에 의해 결정되는 자료구조
• 평균 상수 시간에 삽입, 삭제, 검색을 할 수 있다.

• 해시 함수 h를 사용하여 키 k를 T[h(k)]에 저장한다.

  • T: 해시 테이블; (T[1]: 해시 테이블의 인덱스 1번 엔트리)
  • h: U → {0, 1, ..., m-1}
  • U: 가능한 모든 키들의 집합
  • m: 해시 테이블의 크기
  • h(k): 입력 키 k에 대한 해시 값
  • 키 k에 대한 해시 테이블의 저장 위치를 나타낸다.

저장/검색의 복잡도

1. 순차 검색 (배열): $O(n)$
2. 이진 검색 트리: 최악의 경우-$O(n)$ / 평균-$O(logn)$
3. 균형 잡힌 이진 검색 트리 (ex: AVL 트리, 레드 블랙 트리): 최악의 경우-$O(logn)$
4. 해시 테이블: 평균 $O(1)$

적재율 (Load Factor)

해시 테이블에 원소가 차 있는 비율은 해시 테이블의 성능에 메우 중요한 영향을 미친다. 해시테이블에 원소가 얼마나 차 있는지 나타내는 수치를 적재율 (Load Factor)이라고 한다. 즉, 해시 테이블에서의 검색 효율은 적재율과 밀접한 관련이 있다.

적재율이 높아지면 일반적으로 해시 테이블의 효율이 떨어진다.

해시 테이블의 크기가 $m$이고, 저장된 원소의 총 수가 $n$일 때 적재율은 $\alpha=\frac{n}{m}$으로 표기한다.

일반적으로 임계값을 미리 설정해 놓고 적재율이 이에 이르면 해시 테이블의 크기를 두 배로 늘인 다음 해시 테이블에 저장되어 있는 모든 원소를 다시 해싱하여 저장한다.

2. 해시 함수 (Hash function)

해시 함수는 키 값을 입력으로 받아 해시 테이블 상의 주소를 리턴한다. 좋은 해시 함수는 다음의 조건들을 만족한다.

• 입력 원소가 해시 테이블에 고루 저장되어야 한다. (가장 중요)
• 해시 값이 키의 특정 부분에 의해서만 결정되지 않아야 한다.
• 계산이 간단해야 한다.

해시 함수 구현 방법

1. 나누기 방법 (Division Method)

   • $h(x) = x\ mod\ m$
   • $m$: 해시 테이블 크기

2. 곱하기 방법 (Multiplication Method)

   • $h(x) = (xA\ mod\ 1) \times m$
   • $A: 0 < A < 1$ 인 상수

2.1. 해시 함수: 나누기 방법

• $h(x) = x\ mod\ m$
• ex) $m = 20\ and\ x = 91 ⇒ h(x)=10$
• 장점: 한 번의 mod 연산으로 계산되므로 빠르다

• 단점

  • 특정 $m$ 값에 대해서는 해시 값이 키 값의 특정 부분에 의해 결정된다.
  • $m=2^p$라면, 입력 원소의 하위 $p$ 비트에 의해 해시 값이 결정된다.
  • $m=16$ 일 때, 2561(0xA01), 2577(0xA11), 2593 (0xA21)은 모두 해시 값이 1이다.
  • $m$을 소수로 선택하면 해결 가능하다

2.2. 해시 함수: 곱하기 방법

• $h(x) = m(xA\ mod\ 1)$
• $A: 0 < A < 1$ 인 상수

• $x$의 주소 결정 방법

  • $xA$의 소수부만을 택한다.
  • 소수부에 $m$을 곱하여 정수부를 취한다
• 나누기 방법과 달리 $m$은 소수(prime number)일 필요가 없으며 보통 컴퓨터 환경에 맞게 $m=2^p$로 잡는다.
• 대신 상수 $A$ 값이 해시 값 분포에 많은 영향을 끼치는데 크누스는 $A = {{\sqrt{5}-1} \over {2}}$를 제안하였다.

• ex) $m=8, x=21$

  $\begin{aligned}&A =13/32\\ &xA=21\times13/32=273/32=8+17/32\\ &m (xA\mod\ 1) = 8\times17/32=17/4=4.\ ..\\ &h(21)=4 \end{aligned}$