[자료구조] Hash Table

Hash Table

key를 배열에 mapping하여 삽입/삭제/검색에 사용하는 자료구조. 배열에 key값들이 들어있어서 HashTable이라 한다.
시간복잡도는 $O(1)$의 우수한 성능을 보임
컴퓨터에서는 모든 문자를 숫자로 저장할 수 있음.
따라서 문자도 숫자로 치환하여 저장 가능
e.g) ABC는 각각 ASCII로 65,66,67임. 각 자리수에 대해 128진수로 바꿔주면 $65_128^2 + 66_128^1 + 67*128^0 = 1,073,475$ 이므로 ABC는 1,073,475로 저장된다.

현실적으로 봤을 때 ABC만해도 7자리 자연수로 반환되는데 긴 문자열들은 상상도 할 수 없을만큼 길 것이다. 따라서 해슁된 결과를 m으로 나눈 나머지를 value로 사용하면 메모리에 대한 문제는 해결할 수 있다. m으로 나누게 되면 결과값은 (0, m-1)까지 가지게 된다.(65를 10으로 해슁하면 5)
다만 해쉬 충돌의 문제가 발생하게 된다.

해쉬 충돌

해쉬함수를 h(x): x는 key. 10은 해싱하는 값으로 가정해보면, h(65)=5, h(70)=0, h(35)=5가 된다.
여기서 문제는 h(65)와 h(35)의 값이 같다는 점이다.
따라서 key값인 65와35는 같은 메모리에 mapping 된다.

2가지 기법을 배워보자

1. Chaining
2. open address

Chaining 기법

h(65)와 h(35)의 값이 중복되니 이를 해결하기 위한 방법은 연결리스트를 만드는 것이다.
HashTable을 H라 하자. H[65]=5고 H[35]=5 이다. 논리적으로 보면 H[x]=5가 되는 배열에는 연결리스트로 key들이 저장되어 있다.
H[x]=5 {65, 35}
이런식으로 각 배열방을 연결리스트로 만들어주면 해쉬충돌을 해결할 수 있다.

SUHA(Simple Uniform Hashing Assumption)

각각의 key가 모든 배열방들에 균등한 확률로(eually likely) 독립적으로 해슁된다는 가정.
현실적으로 해쉬는 랜덤하게 해슁되지 않으므로 불가능.
성능분석을 위해서 주로 하는 가정.(논문같은거 쓸 때 유용할 듯)

• Load factor a = n/m:
  • n: 테이블에 저장될 키의 개수
  • m: 해쉬테이블의 킉, 연결리스트의 개수
  • 각 슬롯에 저장된 키의 평균 개수
• 연결리스트 T[j]의 길이를 $n_j$라고 하면 $E[n_j] = a$
• 만약 $n=O(m)$이면 평균검색시간은 $O(1)$

open address 기법

모든 키를 hashtable 자체에 저장하는 것을 open addressing이라 하고, 해쉬 충돌 문제가 발생한다.
충돌 해결 기법은 본문에서는 3가지를 다룬다.
+ Linear probing
+ Quadratic probing
+ Double hashing

Linear probing

h[2]=c, h[3]=f, h[6]=j가 mapping 되어 있는 상태로 가정하자.
h(k)는 2를 가질 경우 h(c)와 중복되게 된다.
linear probing에서는 값이 있을 경우 다음 칸에 삽입한다.
이 경우에는 h[3]에 k가 삽입되어야 하지만 h[3] 또한 f가 자리잡고 있으므로 빈 자리인 h[5]에 삽입된다.

특징
* circular하게 돌아감
* 해쉬 테이블이 가득 차면 삽입을 못함.

Quadratic probing

충돌 발생시 h(k), h(k)+$1^2$, h(k)+$2^2$, h(k)+$3^2$, . . . 순서로 circular하게 돌아감

Double hashing

서로 다른 두 해쉬 함수 h1과 h2를 이용하여
h(k, i) = (h1(k) + i*h2(k)) mod m

open address에서 삭제 문제

h(a), h(b), h(c)가 모두 해쉬충돌하여 h[1]에 배정받았고 linear probing으로 한칸씩 밀려 h[1]=a, h[2]=b, h[3]=c가 되었다고 하자.
a를 지우고 b를 찾게 되면 h[1]은 삭제된 상태에서 h(b)=1을 찾을 수 없게 된다. 이를 해결하기 위해서는 remove된 상태를 기록하여 다음 index를 찾는 방법이 있지만 이는 좋은 방법이 아니다.

좋은 해쉬 함수는 해쉬함수값을 불규칙적으로 되도록하여 해쉬충돌을 최소화 해야한다.(키의 특정 부분(e.g 패턴 등)에 의해서만 결정되지 않아야 함)

해쉬 함수에 대한 기법

Division

거의 모든 해쉬함수가 마지막 단계에서 처리하는 기법. mod 연산을 사용하여 구현한다.
h(k) = k mod m
e.g) m = 20, k = 91일 때, h(k) = 11

장점
+ 한번의 mod연산으로 계산. 빠름
단점
+ 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. $m=2^p$이면 키의 하위 p비트가 해쉬 함수의 값이 됨. 해쉬테이블은 2의 지수꼴로 만드는 경향이 있음.

Multiplication

1. 0에서 1사이에 상수 A를 선택
2. kA의 소수부분만 선택
3. 소수 부분에 m을 곱한 후 소수점 아래를 버림

e.g) m = 8, word size = w = 5, k = 21

1. A = 13/32 선택
2. kA = 21*13/32 = 273/32 = 8 + 17/32
3. m * (kA mod 1) = 8 * 17/32 = 17/4 = 4...
4. h(21) = 4

구현

github