資料結構-雜湊

考研相關文章參考資料為 wjungle 大神提供的筆記

Hashing

• 一種資料儲存與搜尋的機制，當想要存入或取出資料時，先經過 Hashing Function 求出 Hashing Address，接著到 Hash Table 中對應的 Bucket 存入或取出資料 $x$
• Hash Table 由 $B$ 個 Bucket 組成
  • 每個 Bucket 則由 $S$ 個 Slots 組成
    • 每個 Slot 可儲存一筆資料
• 優點:
  • 資料搜尋前不用經過排序
  • 在沒有 Collision 的情況下，資料搜尋時間為 $O(n)$
    • Worst case: $O(n)$: Hashing Function 為定值
  • 保密性、安全性高
    • 不知道 Hashing Function 則無法存取資料
    • 不可回推
  • 常用於密碼學、資料壓縮

相關術語

• Collision 碰撞
  • 不同資料經過 Hashing Function 後得到相同 Hashing Address
• Overflow 溢位
  • Collision 發生後對應的 Bucket 沒有多餘空間可存入資料
  • 有 Collision 不一定有 Overflow
  • 當每個 Bucket 只有一個 Slot 則 Collision = Overflow
• Indentifier density & Loading density
  • 令 $T$ 為 Indentifier 總數，$n$ 為目前使用的 Indentifier 個數，$B*S$ 為 Hash Table szie，則:
    • Indentifier density: $\frac{n}{T}$
    • Loading density: $\frac{n}{B*S} = \alpha$

Hashing Function Design

• 良好的 Hashing Function 應滿足以下三個條件:
  • 計算簡單
  • Collision 少
  • 避免 Hash Table 偏重 (局部) 儲存的情況，應該均勻分布
• 相關名詞:
  • Perfect Hashing Function: 保證無 Collision 發生
  • Uniform Hashing Function: 資料均勻分布於 Hash Table
    • 每個 Bucket 約有 $\frac{n}{B}$ 的資料

middle square

• 將資料數值平方後取中間適當位置之數值作為 Hashing Address
  • ex: $8125^2 = 660\underline{156}25 \Rightarrow 156$

Division (Mod)

• $H(x) = x \% M$
  • $M$ 的建議選擇:
    • 質數
    • 不要整除 $r^k \pm a$，其中 $k, a$ 為很小的正數

Folding Addition

• 將資料切分為幾個相同長度的片段，並將這些片段相加得到 Hashing Address
• 這些片段有兩種相加方式:
  • Shift (直接相加)
  • Boundary (偶數片段反向)
• ex: $x = 123\underline{203}241\underline{112}20$
  • Shift: $123 + \underline{203} + 241 + \underline{112} + 20$
  • Boundary: $123 + \underline{302} + 241 + \underline{211} + 20$

Digits Analysis

• 分析所有資料的各個位數情況:
  • 如果該位數的數值很集中，則捨棄該位數
  • 如果該位數的數值很分散，則挑選該位數
• 由挑出的位數組合成 Hashing Address
• ex:
  • $02-23\underline{2}11\underline{1}0\underline{7} \Rightarrow 217$
  • $02-23\underline{5}11\underline{4}0\underline{7} \Rightarrow 547$
  • $02-23\underline{3}11\underline{5}0\underline{9} \Rightarrow 359$
  • $02-23\underline{4}10\underline{2}0\underline{8} \Rightarrow 428$

Overflow 處理

Linear Probing (線性探測)

• 又稱 Linear open addressing mode
• 當 $H(x)$ 發生 overflow，則探測 $(H(x) + i) \% B, i = 1,2,...,B - 1$，直到有空 Bucket 或是 Table 全滿 (無法存入) 為止
• 優點:
  • 簡單，容易實施
  • 保證 Table 空間充分利用
• 缺點:
  • 易發生 Primary clustering 問題
    • 相同 Hashing Address 的資料會儲存在鄰近的 Bucket 中，增加搜尋時間

Quadratic Probing (平方探測)

• 當 $H(x)$ 發生 overflow，則探測 $(H(x) + i^2) \% B, i = 1,2,...,\frac{B-1}{2}$，直到有空 Bucket 或是探測之 Bucket 全滿 (無法存入) 為止
  • or $(H(x) \pm i^2) \% B$
• 優點:
  • 解決 Primary clustering
• 缺點:
  • 不保證 Table 空間充分利用
  • 易發生 Secondary clustering 問題
    • 相同 Hashing Address 的資料 overflow 之探測位置皆相同 (具有規律性)，增加搜尋時間

Double Hashing

• 當 $H_1(x)$ 發生 overflow，則探測 $(H_1(x) + i * H_2(x)) \% B, i = 1,2,...$，直到有空 Bucket 或是探測之 Bucket 全滿 (無法存入) 為止
  • $H_2(x)$ 的意義: 探測距離
  • $H_2(x)$ 的形式通常為 $H_2(x) = R - (x \% R)$，$R$ 為質數
• 優點:
  • 解決 Secondary clustering
• 缺點:
  • 不保證 Table 空間充分利用

Chain

• 將具有相同 Hashing Address 的資料放入同一 Bucket 中，彼此以 Link list 方式串聯，屬於 close addressing mode (介紹的其餘方式皆為 open addressing mode)

Rehashing

• 提供一系列的 Hashing Functions $H_1(x), H_2(x), H_3(x),..., H_m(x)$，若使用 $H_n$ 發生 overflow，則改用 $H_{n+1}$，直到有空 Bucket 或是函數全部用完 (無法存入) 為止