[Algorithm Part 1] 10. Hash Table

이전 글에서는, 균형 검색 트리(balanced search tree)로 symbol table을 만들어 $\lg N$ 성능 보장을 보였다.
이번 글에서는, symbol table의 또 다른 설계 방식인 hash table에 대해 살펴볼 것이다.
Hash table은 ordered ops(e.g., range search)를 지원하지 않는 대신 보다 좋은 성능을 보여준다.

---

Definition of Hash Table

key-indexed table(=array)에 <key, value> item을 저장한다.
이때, hash function(=key를 array index로 반환해주는 함수)를 이용해 저장 위치를 찾는다.
이전 tree기반의 symbol table과 다르게, hash table기반의 symbol table은 equal 연산을 이용한다.

Issues

1. 좋은 Hash function 찾기 
2. Collision resolution = 동일 index로 hashing된, 서로 다른 key 처리하기

Hash function

좋은 hash function은 2가지 조건을 만족시켜야 한다.

1. 연산 시간이 빨라야 한다.
2. 각 index가 균일한 확률로 생성돼야 한다.

예를 들어, 전화번호 앞자리 2 ~ 3개를 key로 사용하는 것은 매우 부적절하다.
이는 지역을 나타내는 숫자이여서, 2번째 조건에 부합하지 않다.
때문에, 전화번호 앞자리보단 뒤자리를 사용하는 것이 적절하다.
 
다음 예로는, 모든 문자를 이용하는 문자열 hash function은 1번 조건에 부합하지 않는다.
길이가 매우 긴 문자열일 경우, 모든 문자를 사용해야 하기에 연산 시간이 길어지기 때문이다.
그래서, 모든 문자를 사용하는 대신 일부분만 사용하는 것이 적절하다.

Uniform hashing assumption

각 key가 균일한 확률로 생성된다면, 다음과 같은 결과가 도출된다.

1. 평균적으로 $\sqrt (\pi M/2)$개 item이 table에 들어 왔을 때, 충돌이 생긴다.
2. 평균적으로 $M \ln M$개 item이 table에 들어 왔을 때, 모든 index에 적어도 1개 이상의 key가 배정된다.

---

1. Seperate chaining

Data Structure

크기가 M개인 배열을 생성한 후, 각 entry마다 linked-list를 유지한다.
실무에서는, M의 크기를 N/5 크기로 사용한다.

Operations

1. insert

1. hashing: hash function을 통해 0 ~ M-1 사이의 key's index(=i)를 구한다.
2. i번째 linked-list를 순차적으로 탐색한다.
3. 이때 같은 key가 있을 시, 기존 <key, value>를 수정한다.
4. 없을 시, 맨 앞에 <key, value> 노드를 추가한다.

2. search

1. hashing: hash function을 통해 0 ~ M-1 사이의 key's index(=i)를 구한다.
2. i번째 linked-list를 순차적으로 탐색한다.
3. 같은 key가 있을 시, value를 반환한다.
4. 없을 시, null를 반환한다.

---

2. Linear probing (=Open addressing)

Idea 

충돌이 발생했을 시, 다음 index로 이동하여 빈 공간을 찾는다.

Data Structure

크기가 $M$개인 배열을 생성한다. 이때, M은 N(=hash table에 들어 있는 객체 수)보다 커야 한다.

Operations

1. insert

1. hashing: hash function을 통해 0 ~ M-1 사이의 key's index(=i)를 구한다.
2. 해당 index가 비어 있으면, <key, value>를 집어 넣는다.
3. 만약 그렇지 않으면, 다음 index로 이동한다.
4. <key, value>를 넣을 때까지, 2 ~ 3번을 반복한다.

2. search

1. hashing: hash function을 통해 0 ~ M-1 사이의 key's index(=i)를 구한다.
2. 해당 index가 비어 있으면, null를 반환한다.
3. 해당 index에 <key, value>가 저장되어 있으면, 탐색 key와의 동일성을 확인한다.
4. 탐색 key가 동일하면, 해당 index의 value를 반환한다.
5. 탐색 key와 동일하지 않으면, 다음 index로 이동한다.
6. 2 ~ 5번을 반복한다.

---

Performance

seperate chaining은 해싱이 균일하다고 가정할 시, linked-list의 key 개수는 N/M일 확률이 1로 수렴한다. 때문에, equal 연산 횟수는 N/M이다.
 
linear probing hash table은 불필요한 메모리 사용을 줄이기 위해 만들어 졌다.
하지만, hash table의 크기를 매우 타이트하게 구성(=객체 수에 맞게)하게 되면,
cluster(=a contiguous block of items)가 생길 확률이 높아지고, 이는 성능 저하의 원인이 된다.
그렇다고, 크기를 매우 널널하게 구성하면, 불필요한 메모리 사용이 될 수 있기에, 적절한 크기로 구성해야 한다.
 
Hash table의 크기가 M이고, N(=$\alpha$M)개의 객체를 포함시키고 있다고 가정할 때, 평균 연산 횟수는 다음과 같다. 
$$\underset{search hit}{\sim \frac{1}{2} \left( 1 + \frac{1}{1 - \alpha}\right)} \quad\underset{search miss / insert}{\sim \frac{1}{2} \left( 1 + \frac{1}{(1 - \alpha)^2}\right)}$$
 
위 결과를 바탕으로, hash table의 크기를 객체 수의 2배 ($\alpha$ = 1/2)로 맞추는게 적절하다.

	worst case			average case
	search	insert	delete	search-hit	insert	delete
BST	N	N	N	$1.39\lg N$	$1.39\lg N$	$\sqrt N$
2-3 Tree	$c\lg N$	$c\lg N$	$c\lg N$	$c\lg N$	$c\lg N$	$c\lg N$
Red-Black Tree	$2 \lg N$	$2 \lg N$	$2 \lg N$	$1.00 \lg N$	$1.00 \lg N$	$1.00 \lg N$
seperate chaining	$\lg N$	$\lg N$	$\lg N$	3-5	3-5	3-5
linear probing	$\lg N$	$\lg N$	$\lg N$	3-5	3-5	3-5

---

seperate chaining vs linear probing

	seperate chaining	linear probing
memory usage	many	small
hash function	less sensitive	more sensitive

seperate chaining은 hash function에 덜 민감한 반면, 메모리 사용량이 많다.
linear probing은 메모리 시용량이 적은 반면, hash function에 민감하다. 
hash function에 민감하다는 것은 "hash function 성능에 따라 cluster 크기 변동이 심하다"를 뜻이다.

hash table vs balanced search tree

	hash table	balanced search tree
advantage	fast	ordered ops
disadvantage	no ordered ops	slow

hash table은 평균 연산 속도가 빠른 반면,
1). (hash function이 잘못 설계될 경우) 연산 속도가 매우 느려지며, 2). ordered ops일 지원하지 않는다.
balanced search table은 1). $\lg N$ 연산 속도를 보장하며, 2). ordered ops를 지원하는 반면,
평균 연산 속도가 hash table보다 느리다.

---

Application of Symbol Table

Exception filter (e.g., whitelist filter, blacklist filter): 

1. whilelist( or blacklist) 단어 목록 파일을 읽는다.
2. key를 whilelist( or blacklist) 단어로 두는 symbol table을 만든다. 이때 value는 없다.
3. 모든 whilelist (or blacklist) 단어를 symbol table에 추가한다.
4. 문자열이 입력값으로 주어졌을 때, symbol table에 포함된 단어만 (or 포함되지 않는 단어만) 출력한다.

Dictionary:

1. CSV(comma seperate value) 파일을 읽는다.
2. CVS 필드 중, key 필드와 value 필드를 정한다.
3. CVS 파일의 모든 레코드의 key 필드와 value 필드를 symbol table에 추가한다.

File Indexing: 파일 목록이 주어졌을 때, 질의 문자열을 포함하고 있는 모든 파일을 찾아주는 함수

1. 파일 목록을 읽는다.
2. key를 단어, value를 해당 단어를 갖고 있는 파일 목록으로 두는 symbol table을 만든다. 
3. 각 파일의 모든 단어를 symbol table에 추가한다.

Concordance: 말뭉치가 주어졌을 때, 질의 단어를 포함하는 문자열을 모두 찾아주는 함수

1. 말뭉치를 읽는다.
2. key를 단어, value를 해당 단어의 위치 목록으로 두는 symbol table을 만든다. 
3. 말뭉치의 모든 단어를 symbol table에 추가합니다.

Sparse Vectors: sparse vector를 크기가 N인 배열로 표현하지 않고, iterable한 symbol table로 표현한다.

1. key를 vector index, value를 원소 값으로 두는 symbol table을 만든다.
2. 0이 아닌 모든 entry를 symbol table에 추가한다.
3. iterable 연산을 통해 dot product의 연산 횟수가 # of non-zero value로 줄어든다.

Sparse Matrix: sparse matrix를 크기가 $N^2$인 배열로 표현하지 않고, 크기가 N인 symbol table의 배열로 표현한다.

1. 각 열을 sparse vector symbol table로 표현한다.
2. iterable 연산을 통해 matrix-vector product의 연산 횟수가 # of non-zero value로 줄어든다.