Chapter 4. Randomized Algorithms (3)

Chapter :  CLRS 5, 7, 9.2, 10

 

1. Bogosort
2. Randomized Quicksort
3. Randomize Select
4. Majority Element
5. Direct Address Tables
6. Hash Tables
7. Hash Functions
8. Universal Hash Families
9. Open - Addressing

 

---

Hash table이란 sort of data structure으로 빠른 Insert/Delete/Search를 제공합니다.

Hash table에서 Hash Family, 그리고 Universal Hash Tables까지 살펴보도록 하겠습니다.

 

---

Direct Addressing

 

이 Hash family에서 목표는 Insert, Delete, Search 를 O(1) time 안에 하는 것입니다.

0-2	3-5	6-8	9-11	12-14	15-17	18-20	21-23	24-26	27-29
1 0	3	7		13 12	17 16 15	20			27 28

처럼 한다면 거의 O(1) 안에 할 수 있겠지만, 매우 많은 공간이 필요합니다. 다른 방법을 써보죠.

---

Hash Tables , Hash function

 

일단 Hash Table에 대해 알아보기전에, 전체 set인 Universal set의 크기가 M 이며 M이 매우 크다고 가정합니다.

그러나 bucket의 크기인 n은 그것보다 작습니다.

 

U의 원소를 mapping하는 hash function이 있고 이는 h 입니다. (h:U → {1,…,n} )

 

예를 한번 들어봅시다

 이 방식을 Hash Table (with Chaning) 이라고합니다.

 

이 방식은, 좋을수도 나쁠수도 있겠죠?

만약 13 43 53 23이 줄줄히 들어온다면 search 의 time이 O(n)에 가까워집니다.

 

저런식으로 Worst Case가 계속 생긴다면 어떻게 Hash를 해야 할까요?

 

Random을 도입해서 WortCase가 아닌 Expected Analysis를 해야합니다.

---

Hash Family

 

hash function 을 uniformly random function 이라고 해볼까요?

 

그렇다면 Bucket당 담겨있는 숫자가 2 이하이므로 평균적으로 Insert/Delete/Search에 걸리는 시간은 O(1)이 될 것입니다.

 

나쁜 소식이 있습니다.

보기에는 좋아보이는데 이게 뭐가 문제일까요?찾을때 필요한 function이 random이라서 Search에 필요한 Key를 찾을 수 없다는거죠

 

만약 Key를 저장한다고 하더라도 function을 전부 저장해야 하기 때문에모든 hash functions의 사이즈를 합하면 n^M에 달하고, 저장공간은 Mlog(n) bits 가 필요합니다. (-> 너무 커요! )

 

 

이를 해결하는 방법이 바로 Hash family = {h0,h1,h2...} 를 만들어서 그 안에서만 random성을 주는 것입니다.

---

Universal Hash Family

그럼 Hash family 를 제대로 뽑는 방법은 무엇일까요?

를 1/n보다 작도록 만드는 것입니다.

 

이런 hash family의 예시가 무엇이 있을까요?

 

(Example)

 

M 보다 큰 prime number인 p를 하나 뽑고

 

f_a,b(x) =  ax + b (mod p)

h_a,b(x) =  f(x) (mod n)

 

𝐻 = { ℎ_a,b(𝑥) ∶ 𝑎 ∈ {1, … , 𝑝 − 1}, 𝑏 ∈ {0, … , 𝑝 − 1} }

 

에서 a,b를 랜덤으로 뽑아 hash 해주는 것입니다.

 

그렇다면 Space는 얼마나 필요할까요? 

 

|H| = p(p-1) = O(M^2)

log(M^2) = O(log(M))

 

Direct addressing에 비해서도 적은 Space가 필요합니다.

---

Summary

 

 INSERT/DELETE/SEARCH 가 O(1)에 되도록 만드는 것이 hash table의 목적입니다.

 

Hash function이란 h : U -> {1,2,3,4,......,n} 을 mapping하는 함수입니다.

 

	장점	단점
Direct addressing	O(1) INSERT/DELETE/SEARCH	저장공간 너무 큼
Hash table with chaining	저장공간 작음	search 시간이 O(length(list))
Deterministic hash function		O(1) search를 할 수 없음
Uniformly random hash function	O(1) search가 됨	random hash function을 저장하기에 공간이 너무 부족함