11장 Hash Table

1. Direct-address tables
키가 n개 있으면 테이블의 크기도 n개
키를 테이블에서 찾는 것, element를 삽입하는 것, 삭제하는 것 모두 running time O(1)
전체 키에서 실제 사용되는 키가 적을 경우 공간 소비가 심하다.
O(1)를 유지시키면서 공간을 줄일 수 있는 방법이 없을까?

2. Hash tables
Hashing
키를 해쉬함수에 넣어서 나온 값으로 hash table에 들어갈 위치를 정하는 것.
Collision
두 키의 Hashing 결과 같은 위치를 가질 때
테이블의 크기가 키크기보다 작기 때문에 collision을 피할 수 없다. collision을 최소화하도록 한다.
어떻게? Hashing function을 잘 만들기.

Collision이 발생하였을 때 해결하는 방법

i) Channing
두 키가 해시테이블에서 같은 위치(collision)일 경우 리스트에 element를 추가한다.
리스트가 길 경우 찾는 시간이 늘어난다. 

load factor
해쉬테이블의 성능 분석 척도
α = n/m (엘리먼트 갯수/슬롯의 갯수)
worst case
모든 키가 테이블의 한 슬롯에만 들어갈 때.

ii) Open addressing
모든 값들이 해시테이블 내에 저장된다. 리스트가 없고 테이블 밖에 element가 저장되지 않는다.
element를 찾을때까지 table slot을 조사한다.
load factor가 1을 넘지 않는다.
포인터 안써도 되고, 리스트일때 사용되지 않던 메모리 공간을 slot으로 이용할 수 있다.

probe : 삽입할 때 slot이 비어있는지 아닌지 확인하는 것.
probe sequence에 따라 slot을 조사한다.

Deletion : search할 때 멈추는 것을 막기 위해서 비워두지 않고 'Deleted' 같은 특별한 표시를 해놓는다.

probing 방법

i) Linear probing
h(k')에 값이 있으면 (h(k') + i) mod m 을 조사(i는 0,1,2,3, ... m-1)
단점
primary clustering : 채워져 있는 slot들이 한곳에 모일 가능성이 높다. i번째까지 가득찬 slots이 있을 때 다음 slot이 가득찰 확률은 (i+1)/m이기 때문에. 평균 search 시간이 늘어난다.

ii) Quadratic probing
h(k, i) = (h'(k) + c1*i + c2*i^2) mod m을 이용
단점
linear probing의 primary clustering은 발생하지 않지만
secondary clustering이 발생. 즉 두 키가 같은 해시값을 가지면 probe하는 위치가 같다.
linear probing처럼 처음 probe 하는 위치가 모든 probing sequence를 결정한다.

iii) Double hashing
h(k,i) = (h1(k) + i*h2(k)) mod m
h1에 의해 같은 값을 갖게 되더라도 h2에 의해 다른 값을 가져서 다른 해쉬값을 가질 수 있다.
따라서 h2가 모든 테이블의 slot를 탐색할 수 있도록 잘 설계되어야 한다.
예를 들어 h1(k1) = 0 이고 h2(k1) = 2일 경우 홀수 slot만 간다.

3. Hash functions

각각의 키가 hash table의 slot에 고르게 들어가도록 hash function을 만든다.
The division method
key k를 m으로 나눈 나머지값이 해쉬값이 된다.
i) m이 2^p 일때,
h(k)의 값은 k의 뒷부분 p bits이다.
ii) m이 2^p-1 일 때,
k는 2^p진법으로 표현 가능하다.
k의 자리수만 바꾼 값들은 k와 해시값이 같다. (각 자리를 modular한 합이 같기 때문에)

좋은 m값
2의 지수승과 가깝지 않은 소수

The multiplication method
key값에 소수인 A를 곱해서 나온 수에서 소수부분에 m을 곱하여 나온 수에서 정수부분이 헤시값이 된다.