Hash function

1. Hash Function
一種資料儲存與擷取技術，用來將 actual key 轉成 hashing address，再依此位置到 hash table 中進行資料的存取。

2. Loading Denisty
α = n / b ；其中 n 為資料數，b 為 bucket 數。

3. 良好的 Hash Function 該具備條件
計算宜簡單，碰撞要少，不要有偏重的問題

4. 常見的 Hash Function 有

Middle Square：將鍵值平方後，取中間某些位元(bits)。
Modulation：除法之後取餘數。
Folding Addition：把數字折疊後相加。

5. Collision
不同的鍵值經由 Hash Function 計算後，對應到相同的 Hashing Address。即：兩個不同鍵值 X、Y，H(X)=H(Y)

6. Overflow
當 Collision 發生時，且無多餘的空間可以存放資料。

7. Overflow 處理方式

(a) linear probing：當 H(x) 發生碰撞時，則延著 H(x)+1、H(x)+2 向下找。
(b) Quadratic Probing：碰撞時改用 [ H(x) ± i^2 ] % n
(c) Double Hashing：碰撞時用 H(x) + i*G(X)；其中 G(X) = R-(X%R) , R為質數
(d) Chaining

8. 使用 Chaining 方法下，平均成功(Sn)、失敗(Un)次數。其中 α = n/b

Sn = 1 + α/2
Un = α

9. Binary Search 與 Hash Function
比較資料要經過排列 || 資料不用經過排列
O(logN) || O(1) 未碰撞時
Actual key search || Transformation key search
不用處理 overflow || 要處理