Hashing

雜湊

雜湊的定義：為一資料「儲存」與「搜尋擷取」之機制。

最適合靜態資料搜尋。
作法：Xff(X)結果
F(X)函數為透過雜湊表來決定之。
Hashing Table中有B個buckets桶子，一個bucket有s個slot槽，每一個slot可放置一筆資料。
Hashing Problem
碰撞（Collision）
定義：不同的Data x, y有可能雜湊後，f(x)=f(y)，這種狀況謂之碰撞。
溢位（Overflow）
定義：當有碰撞發生時，且Bucket沒有多餘slot可以儲存。
有碰撞不一定有溢位；有溢位必定有碰撞。
One Bucket, One slot. 有碰撞有溢位；有溢位有碰撞。

Hashing Function的設計方法
平方值取中間數：將位值平方，之後擷取中間適當個數值。
Mod法：有b個buckets，則f(x)=x mod b….取餘數
摺疊相加法：
X = 12320324111220
位移摺疊：123+203+241+112+20=699
邊界摺疊：123+302+241+211+20=897

溢位問題處理
1. 線性探測（Linear probing）
2. 二次方探測
3. 再散置
4. Link List

線性探測
由碰撞的空間向下搜尋，未被使用的空間來儲存。
缺點：容易造成資料群聚現象，大量資料會導致碰撞次數增加，搜尋可存空間時間拉長。

二次方探測
解決上述資料群聚現象，當溢位發生時，利用(f(X)+i^2)mod b找另外一個地方。若結果為負值，則需加上b。其中，i值須介於1和(b-1)/2中間。