About hash tables

1. Motivation

- Use array (static set) or linked-list (dynamic set)

- They take linear time for search operation (i.e., proportional to the size)

- Need better method → hash table

(Array/Linked-list의 크기에 비례하는 탐색시간을 줄이는 방법이 필요)

2. Problem

- When a record to be inserted maps to an already occupied slot in hash table, a collision occurs

- You need a good hash function

(높은 확률로 테이블 크기가 데이터보다 작기 때문에 한 슬롯에 배정되는 데이터가 1 이상 → Collision!)

3. Hash Function

- The properties of a good hash function: (1) Even distribution, (2) Irregularness

3.1. Division method: h(k) = k mod m

- Works fine if keys are uniformly distributed (균등하게 분포하는 키에 대해서 효율적)

Ex>

3.2. Multiplication method: h(k) = floor(m*(kA mod 1)), 0<A<1

- Where "kA mod 1" means the fractional part of kA, that is "kA-floor(kA)" (곧, 소수부)

- Choice of m is not critical. Typically chosen as a power of 2 (m = 2^p, for some integer p)

Ex>

4. Collision Resolution

4.1. Chaining

- Use linked-lists. New key inserted at the head of list. 

(Why not inserted at the tail? → it takes linear search time)

- Chaning uses linked-lists: a bit messy

4.2. Open Addressing

- We can seek next available slots in the table when collision occurs

- Search after deletion problem (도중에 비어있어서, 탐색을 멈춤) → 지운자리에 D를 표시

4.2.1. Linear Probing (deterministic method)

- 해당 슬롯이 차있으면, 바로 다음 슬롯으로 이동

- Filled slots in table tend to form clusters (called "clustering problem") 

(특정 구간에 몰리는 클러스터 문제)

4.2.2. Quadratic Probing (deterministic method)

- 해당 슬롯이 차있으면, 1^2, 2^2, 3^2 다음 슬롯으로 이동

- Reduces clusters, but still suffers from clustering problem

(클러스터 문제를 줄일 수는 있지만, 해결은 아님)

4.2.3. Double Hashing (non-deterministic method)

- Deterministic method로는 클러스터 해결 불가

- Non-deterministic method는 클러스터링 문제 해결 가능

- Use two hash function h(k) and h'(k): h(k) - initial probing position, h'(k) - offset