資料結構與演算法筆記 - Hashing (雜湊) 原理介紹
Hashing 定義
是一種資料儲存與擷取之技術，當要存取 Data X 之前，必須先經過 Hashing Function 計算求出 Hashing Address (or Home Address)，再到 Hash Table 中對應的 Bucket 中存取 Data X，而 Hash Table 結構是由 B 個 buckets 組成，每個 bucket 有 S 個 Slots，每個 Slot 可存一筆 Data
=> Hash Table 大小 = B * S 筆
Hashing 優點
-
搜尋 Data 之前，無需事先排序過
-
再沒有 Collision 情況下，Search X 之 time 為: O (1)，與資料量 n 無關
-
保密 / 安全性高，在不知道 Hashing Function 下，很難取得 Data
-
可作為 Data 壓縮之用途
例如：Unix 之 password 採用一對一，不可逆之 Hashing
何謂 Collision (碰撞)？
不同的 Data，例如 (x,y)，經過 Hashing function 計算後得出相同的 Hashing Address 稱之，也就是 H (x) = H (y)。
何謂 Overflow (溢位)？
當 Collision 發生後，且對應的 Bucket 已滿，則稱為 Overflow
Collision 與 Overflow 比較
- 有 collision 不一定會 overflow
- 若每個 bucket 只有 1 個 slot，或是只能放一筆 Data，則 Collision = Overflow
identifier density 與 loading density
令 t 為 identifier 是 Hash table 裡面的總數，n 為使用 identifier 個數，B * S 為 Hash Table size
則：
-
$$
identifier, density, = \frac{n}{t}
$$ -
$$
loading, density,(負載密度) = \frac {n}{B * S}
$$
Note：若 load density 越大， 代表 Hash Table 利用度高，但相對 Collision 機會也大
Hashing Function Design 雜湊函數設計
好的 Hashing Function 設計，要滿足下列三個 criteria：
- 計算宜簡單，不要過度複雜
- Collision 要少
- 不要造成 Hash Table 局部儲存之情況，要夠均勻才好
Perfect Hashing Function
此函數保證不會發生 Collision
Uniform Hashing Function
n 個 Data 存入 Hash Table 之 B 個 Bucket 時，每個 Bucket 內之 Data 個數大約相等，即 n / B，則此函數為 Uniform (均勻的)
常見的 Hashing Function 設計
Middle Square
將鍵值平方後，取中間適當位數作為 Hashing Address
例如：鍵值 = 8125，平方後， = 66015625
取中間三個位數，156 作為 Hashing Address
Mod (or Divide) 取餘數
H(X) = X % M
M 最好滿足：
- 質數 (除盡 1 和除盡自已)
- M 不宜為 2 (求得的位址僅有 0 或 1，collision 的機會很大)
Folding Addition
將鍵值切成幾個相同長度之片段 (P1~Pn)，再將這些片段加總，即得 Hash Address
而相加的方法有兩種：
- shift (位移)
- bounding (邊界)
例如：x = 12320324111220
切成這樣：
P1 = 123
P2 = 203
P3 = 241
P4 = 112
P5 = 020
-
shift 作法
將 P1~Pn 相加 = 699
-
bounding 作法
偶數的片段反向，所以：
P2 = 302
P4 = 211
再加總 P1~Pn = 897
Digits Analysis (位數值分析)
適用於資料事先知道之情況，分析每個資料再不同位數之值域分布情況，若分布很集中，則捨棄該位數，若散亂，則挑選，挑出之位數組成 Hashing Address
拿電話號碼為例：
02-7415089 => 158
02-7434079 => 347
02-7424139 => 243
02-7458069 => 586
02-7473029 => 732
根據以上的位數挑出三個數字的 Hashing Addrss
Overflow 處理方法 (重要)
Linear Probing (線性探測)
當 H (x) 發生 overflow 的時候，則探測 (H (x)+i)% B，B 為 Bucket 數，i = 1,2,3,…,B-1，直到有 Bucket 可存 or Table 全滿為止
優點：
- 簡單、易於實施
- 保證 Table 空間可以充分利用
缺點：
容易發生 Primary Clustering 現象，造成 Search/Insert/Delete X 等時間大幅增加之問題
Primary Clustering 意思：具有相同 Hashing Address 之 Data 容易占用相鄰的 Buckets 存放，形成群聚現象
Quadratic Probing (二次方探測)
當 H (x) 發生 overflow 時，則探測
$$
(H(x)\pm i^2)\text{ % B}
$$
或是
$$
(H(x)+ i^2)\text{ % B}
$$
B 為 Bucket 數目，i=1,2,3…,[B/2]，直到有 Bucket 可存，或探測位置都滿，無法存入為止
優點：
解決 Primary Clustering Problem
缺點：
- 有 Secondary Clustering Problem，因為具有相同的 Hashing Address 之 Data，它們的探測軌跡均相同，後來進來的 Data 仍需花大量時間去探測先前 Data 已經探測的位置，才能找到可用的 Bucket。
- Table Space 不保證可以充分利用
Double Hashing
令 H1 為 Hashing Function，當 H1 (x) 發生 Overflow 時，則探測
$$
(H1(x)+i\times H2(x))\text{ % B}
$$
B 為 Bucket 數目，i 從 1,2,3,…,B-1，H2 (x) 為探測間隔 (Span)，通常形式為
$$
R-(x\text %R)
$$
R 為質數，直到找到空的 Bucket 或是探測位置皆滿為止
優點：
解決 Primary Clustering and Secondary Clustering Problem
缺點：
Table Space 不保證充分利用
Chaining or Link List (鏈結串列)
具有相同的 Hashing Address 的 Data 均置入同一個 Bucket 去，而 Bucket 內之 Data 彼此透過 Link List 結構串連在一起，而這種情況就作 Closed Address Mode。
其他的 Overflow 處理方法是 Open Address Mode。
分析：
最差之 Search Time in chain 是 O (n)，但如果串列裡面結構改用 AVL Tree、R-B Tree 之結構去作，則改善時間為 O (logn)
Rehashing (再雜湊)
提供一系列的 Hashing Function H1~Hm，當 H1 發生 Overflow，則改用 H2，以此類推，直到找到 Bucket 可存，或 Hashing Function 用完為止。
最後最後！請聽我一言！
如果你還沒有註冊 Like Coin，你可以在文章最下方看到 Like 的按鈕，點下去後即可申請帳號，透過申請帳號後可以幫我的文章按下 Like，而 Like 最多可以點五次，而你不用付出任何一塊錢，就能給我寫這篇文章的最大的回饋！