Hashing

1. Static Hashing

static hashing 에서 dictionary pair가 hash table(ht) 에 저장된다. hash table은 b 개의 bucket(ht[0], … , ht[b-1]) 으로 나누어진다. 각각의 bucket은 s 개의 slot으로 나누어진다. key가 k인 dictionary pair의 주소는 hash function에 의해서 결정된다.

n : 테이블에 존재하는 pair의 수, T : 가능한 key의 수, s : 버킷에 존재하는 slot 수

key density : n/T

loading density : n/sb

Hash Function의 종류에는 크게 3가지가 있다.

1. Division : h(k) = k % D 으로 실제 가장 많이 사용된다.

2. Mid-Square : key를 제곱한후 가운데의 bit들을 사용한다. 이렇게 하는 이유는 squared key의 middle bits가 key의 bits에 의존하기 때문이다.

3. Folding : key를 여러 partition으로 쪼갠후, 각각의 partition의 least significant digit이 마지막 파티션의 digit과 정렬되도록 오른쪽으로 shift한뒤, 모두 더한다. 이를 shift folding 방법이라 한다. 말로 하면 복잡하므로 예를 들면 아래와 같다.

   k = 12320324111220 이라 가정하자.

   세자리수 길이로 파티션 하면 P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20 이 된다. 여기서 shift folding을 수행하면 아래와 같다.

   h(k) = P1 + P2 + P3 + P4 + P5 = 123 + 203 + 241 + 112 + 20 = 699

   유사한 다른 방법으로 folding at the boundaries 방법이 있다. 한칸씩 건너뛴 파티션을 뒤집은후 더하는 방법이다. 이 또한 예로 설명하면 아래와 같다.

   위의 예에서 P2와 P4를 뒤집어, 302와 211으로 만든다. 그리고 다섯개의 파티션을 더한다.

   h(k) = P1 + P2 + P3 + P4 + P5 = 123 + 302 + 241 + 211 + 20 =897

Overflow Handling

overflow를 다루는 두가지 방법이 있다. 바로 open addressing 과 Chaining 이다.

Open addressing의 4가지 방법

1. linear probing : 한국말로 번역하면 선형탐색이다. 즉, h(k) % b 라는 key에서 overflow가 발생했을때 ht[(h(k)+i) % b], 0 <= i <= b-1 순서로 비어있는 bucket을 탐색하는 방법이다. hash table이 가득찬 경우 hash table 크기를 증가시켜야 하는데, 보통은 loading density 가 특정 threshold(eg. 0.75) 를 초과할 경우 table 증가를 한다. 왜냐하면 performance가 더 좋기 때문이다. 여기서 주의할 점은 기존에 존재하는 entry들을 새로운 table에 재 맵핑을 해야한다는 것이다. linear probing의 단점은 overflow가 발생할 경우 key들이 한 클러스터에 집중된다는 것이고, 인접한 클러스터들이 서로 섞이는 문제점이 발생하여 탐색 시간이 증가하게 된다.
2. quadratic probing : 클러스터의 크기가 증가하는 것을 막기위한 방법으로 quadratic probing이 있다. 이 방법은 bucket을 다음과 같이 탐색한다 : h(k), (h(k)+i^2) % b, (h(k) - i^2) % b , 1 <= i <= (b-1)/2
3. rehashing : 클러스터 크기증가를 막는 다른 방법으로 rehashing이 있다. 하나의 key에 이 방법은 일련의 hash function을 적용하는 방법이다 : h1, h2 , ... hm.
4. random probing : 다음의 순서로 bucket을 탐색한다. (h(k) + s(i)) % b, 1 <= i <= b-1, where s(i) is a pseudo random number 이때 s(i)는 반드시 i가 1~b-1의 범위에 있을때, 1~b-1 값이 정확히 한번만 리턴하도록 해야한다.

Chaining

Chaining : bucket당 list를 두는 방법이다. 사실 list뿐만 아니라 search, insert, delete를 지원하는 모든 data structure를 사용해도 된다. 예를 들면, array, chain, search tree 등이다. 새로운 key를 chain에 삽입할때, 먼저 해당 chain에 값이 존재하는지 확인해야 한다.

2. Dynamic hashing

TODO

Reference

• Fundametals Of Data Structures in C by Horowitz,Sahni,Anderson-Freed