本教材依「資料結構用的 Hash」與「密碼學用的 Hash」兩條主線編排，並對應 Hash/cpp/ 內的 C++ 範例程式。

目錄

  1. 什麼是 Hash
  2. Hash Function 與為什麼需要 Hash
  3. Hash Table 與 Key–Value
  4. 平均 O(1) 與最壞情況
  5. 碰撞（Collision）與處理策略
  6. Load Factor 與 Rehashing
  7. 常見 Hash Function 設計
  8. 字串多項式 Hash 與 Rolling Hash
  9. Rabin-Karp、Prefix Hash、Double Hash
  10. Bloom Filter
  11. Consistent Hashing
  12. 密碼學 Hash 與密碼儲存
  13. C++ 範例檔案對照表
  14. 編譯方式

1. 什麼是 Hash

Hash（雜湊）的核心想法：透過一個函式 (h)，把「任意大小的輸入」映射到「有限範圍內的輸出」（常見為整數索引）。

  • 輸入：Key（例如字串 "apple"、整數、物件位址等）
  • 輸出：Hash value / Hash code（落在 (0 \ldots m-1) 或類似範圍）
  • 目標：計算要快、分布要均勻，讓後續資料結構（例如 Hash Table）能近似常數時間完成查詢與更新

注意：一般資料結構課程中的 Hash 不要求密碼學上的單向性或抗碰撞；那是另一類「密碼雜湊函式」的要求。

2. Hash Function 與為什麼需要 Hash

2.1 Hash Function 是什麼

Hash function (h(k)) 把 key (k) 映射到表格索引（或某個整數桶）。

理想性質（實務上盡量接近即可）：

  • 可計算性：能在 (O(1)) 或接近常數時間算出 (h(k))
  • 均勻性：不同 key 經 (h) 映射後，大致平均落在各桶，減少碰撞機率
  • 確定性：同一個 (k) 每次得到相同 (h(k))（除非刻意用隨機種子的 Universal Hashing 等特殊設計）

2.2 為什麼需要 Hash

  • 快速查字典：由 key 直接算索引，避免在有序結構上做 (O(\log n)) 搜尋，或線性掃描 (O(n))
  • 去重、計數、快取：Key 對應 value（出現次數、快取內容）
  • 字串演算法：多項式 rolling hash 支援子字串 (O(1)) 更新 hash 值
  • 分散式系統：Consistent hashing 讓節點增減時搬移資料量可控

3. Hash Table 與 Key–Value

3.1 基本結構

Hash table（雜湊表）通常包含：

  • 長度為 (m) 的陣列（桶 / slots）
  • Hash function (h(k)) 把 key 映射到某個 slot
  • 碰撞發生時的處理機制（見第 5 節）

3.2 Key–Value

每個儲存單位是一對 (key, value)：

  • Key：用來索引與比對是否同一筆資料
  • Value：實際要存的內容（數字、字串、指標、結構體等）

操作通常包含：insert(k, v)、search(k)、erase(k)。

4. 平均 O(1) 與最壞情況

在「簡單均勻雜湊（SUHA）」假設下，且碰撞處理得當、Load factor 有上限時：

  • 平均時間：插入、查詢、刪除可視為 (O(1))（均攤分析下 insert 含 rehash 仍常為 (O(1)) 均攤）

最壞情況仍可能是 (O(n))，例如：

  • 大量 key 都碰撞到同一桶（惡意輸入或極差的 (h)）
  • Open addressing 形成長探測鏈

因此實務上會選好的 (h)、控制 load factor、必要時使用 Universal hashing 或 加密安全 的隨機性來對抗攻擊場景。

5. 碰撞（Collision）與處理策略

當 (k_1 \neq k_2) 但 (h(k_1)=h(k_2)) 時稱為碰撞。因為輸出範圍有限而輸入無限，碰撞必然存在（鴿籠原理）；重點是如何處理與如何降低發生後的代價。

5.1 Separate Chaining（鏈結法）

每個桶放一個鏈結串列（或其它結構）存放所有映射到該桶的 (key, value)。

  • 優點：實作簡單、刪除容易、表格不會「物理上滿了就不能插」
  • 缺點：指標間接存取、快取不友善；最壞鏈很長時退化

對應程式：hash_table_chaining.cpp

5.2 Open Addressing（開放定址）

所有元素都存在表格陣列內；碰撞時依探測序列找下一個空位。

Linear Probing（線性探測）

探測序列：((h(k)+1)\bmod m, (h(k)+2)\bmod m, \ldots)

  • 優點：快取局部性好、實作簡單
  • 缺點：容易造成群聚（primary clustering）

Quadratic Probing（二次探測）

探測序列：((h(k)+c_1 i + c_2 i^2)\bmod m)，常見 (c_1=0, c_2=1) 即 ((h(k)+i^2)\bmod m)

  • 優點：減輕 primary clustering
  • 缺點：仍有 secondary clustering；需挑選 (m) 使能走滿足夠多位置（常見條件：(m) 為質數且 load factor (<0.5) 等）

Double Hashing（雙雜湊）

第二個 hash (h_2(k)) 與 (m) 互質相關條件下，探測序列：

[ (h(k) + i \cdot h_2(k)) \bmod m,\quad i=0,1,2,\ldots ]

  • 優點：探測序列更接近隨機，群聚較少
  • 缺點：需設計好的 (h_2)（例如永遠為奇數、與 (m) 互質）

對應程式：hash_table_open_addressing.cpp

6. Load Factor 與 Rehashing

6.1 Load Factor（負載因子）

定義（標準寫法）：

[ \alpha = \frac{n}{m} ]

其中：

  • (n)：目前元素個數
  • (m)：Hash table 槽位數（bucket 數或陣列長度）

6.2 為什麼 Load Factor 太高效能會掉

  • Chaining：鏈變長，查詢變成掃鏈，期望長度與 (\alpha) 成正比
  • Open addressing：空位變少，探測序列變長，群聚更嚴重

6.3 Rehashing

當 (\alpha) 超過門檻（例如 0.7～0.75）：

  1. 配置一個更大的新表（常見新 (m') 為質數或 2 的次方，依實作慣例）
  2. 對舊表每個元素用新的 (m') 重新計算索引
  3. 搬移到新表

均攤分析：偶發 (O(n)) 的 rehash，長期分攤後每次 insert 仍常為 (O(1))。

對應程式：hash_table_chaining.cpp、hash_table_open_addressing.cpp 皆含擴表邏輯。

7. 常見 Hash Function 設計

7.1 Division Method（除法）

[ h(k) = k \bmod m ]

  • 實作簡單
  • 缺點：若 (k) 的低位規律性強，(m) 不當會群聚；常建議 (m) 用質數（非絕對，但常見經驗法則）

7.2 Multiplication Method（乘法）

選常數 (0<A<1)，例如 Knuth 建議 (A \approx (\sqrt{5}-1)/2)：

[ h(k) = \lfloor m \cdot (kA \bmod 1) \rfloor ]

  • 對 (k) 低位分布較不敏感（相對除法低位）

7.3 Polynomial Rolling Hash（字串多項式）

對字串 (s_0 s_1 \ldots s_{n-1})（常把字元映射成整數），選底數 (p) 與模數 (m)：

[ H(s)=\Big(\sum_{i=0}^{n-1} s_i \cdot p^i\Big)\bmod m ]

也可用 (p^{n-1-i}) 的寫法（前綴方向不同，本質相同）；Rolling 時配合前綴與 (p) 的次方做 (O(1)) 滑動更新。

7.4 String Hash（面試常見）

與上式同族；重點是：

  • (p)：大於字元集大小的質數（對 ASCII 常用 131、257 等）
  • (m)：夠大的質數以降低碰撞；競賽常雙模數（double modulus）降低誤判

7.5 Universal Hashing（通用雜湊）

從一族函式 (\mathcal{H}) 中隨機選一個 (h)，使得對任意相異 key (x,y)：

[ \Pr_{h\in\mathcal{H}}[h(x)=h(y)] \le \frac{1}{m} ]

用於演算法分析與對抗刻意製造碰撞的攻擊（搭配密碼學 primitive 則更強）。

對應程式：hash_functions_demo.cpp

8. 字串多項式 Hash 與 Rolling Hash

8.1 應用

  • 子字串 hash 比對
  • 重複子字串偵測
  • Rabin-Karp 模式匹配

8.2 Rolling（滑動視窗）

已知 ([L,R]) 的 hash，要移到 ([L+1,R+1])：減去左端字元貢獻、整段乘上 (p) 的調整（依你定義的前綴方向）、加上右端字元。搭配模逆元或雙模數可避免浮點與溢位問題。

對應程式：polynomial_string_hash.cpp、rabin_karp.cpp

9. Rabin-Karp、Prefix Hash、Double Hash

9.1 Rabin-Karp

用 rolling hash 在文字上滑動，hash 相等時再以字元逐一確認避免 hash 碰撞誤判。期望時間接近線性。

9.2 Prefix Hash

預處理前綴 hash 陣列 (pref[i]=H(s[0..i]))，搭配次方前綴可在 (O(1)) 取得任意子字串 hash（需注意模運算與底數方向）。

9.3 Double Hash

同時維護兩組 ((p_1,m_1))、((p_2,m_2)) 的 hash 對 ((H_1,H_2))；兩者同時相等的碰撞機率近似乘積，大幅降低誤判。

對應程式：rabin_karp.cpp、prefix_double_hash.cpp

10. Bloom Filter

Bloom filter：(m) 位元陣列 + (k) 個 hash 函式。

  • insert(x)：對 (h_1(x),\ldots,h_k(x)) 對應位置設為 1
  • query(x)：若這些位皆為 1 則回傳「可能在集合內」；若有 0 則「一定不在」

特性：

  • 空間極省、查詢快
  • 有假陽性（false positive）、一般設計下難刪除（Counting Bloom 是延伸）

對應程式：bloom_filter.cpp

11. Consistent Hashing

將 hash ring 上分配 key 與節點；新增/移除節點時，只需搬移環上局部區間的 key，避免「節點數變動就幾乎全表重映射」。

常見強化：virtual nodes 改善負載不均。

對應程式：consistent_hashing.cpp

12. 密碼學 Hash 與密碼儲存

12.1 與資料結構 Hash 的差異

密碼學雜湊（如 SHA 家族）要求（強度依版本而異）：

  • 單向性（ preimage resistance）：給定 (y) 難找 (x) 使 (H(x)=y)
  • 抗碰撞：難找 (x\neq x') 使 (H(x)=H(x'))
  • 雪崩效應（Avalanche effect）：輸入改一點點，輸出大幅變化

12.2 常見演算法（概念定位）

名稱 備註
MD5 已不建議用於安全場景；碰撞已被實務攻破
SHA-1 已淘汰於憑證等用途
SHA-256 SHA-2 家族，現今常見
bcrypt 專為密碼設計，內建 work factor（計算成本可調）
PBKDF2 密碼衍生金鑰（KDF），可搭配 HMAC-SHA256 等

12.3 Salt、Rainbow Table、密碼儲存

  • Salt（鹽）：每個使用者一個隨機 salt，與密碼一起送入 KDF/雜湊；使相同密碼產生不同 digest，擊敗預先計算的 Rainbow table
  • Rainbow table：時間與空間折衷的「hash → 常見密碼」查表；有 per-user salt 時攻擊成本大幅上升
  • 密碼儲存最佳實務：使用 bcrypt / scrypt / Argon2 或 PBKDF2（足夠迭代次數），存 salt + digest + 參數；不要自己發明「XOR 幾次」當安全雜湊

12.4 不可逆性（One-way）

對密碼學雜湊 (H)，在計算上應難以從 (H(x)) 還原 (x)（ preimage resistance）。這與 Hash table 用的「非密碼雜湊」不同：後者常可逆推或暴力枚舉小空間的 key，且不要求抗碰撞。

12.5 雪崩效應（Avalanche Effect）

輸入位元極小的變化，會使輸出位元大量變化（近似「半數輸出位元翻轉」）。直觀上讓相似密碼的 digest 看起來毫不相關，也提高差分密碼分析的難度。

12.6 bcrypt 與 PBKDF2 在實務上的角色

  • bcrypt：內建 cost（work factor），並對密碼長度與實作細節有專門考量；許多語言有成熟綁定。
  • PBKDF2：標準化 KDF，常以 HMAC-SHA256 迭代；適合需要 FIPS 或舊系統相容時，但參數要足夠「慢」（迭代次數、記憶體/並行若用 Argon2 更佳）。

對應程式：openssl_crypto_demo.cpp（需 OpenSSL；示範 SHA-256 與 PBKDF2-HMAC-SHA256；不含 bcrypt 綁定，請在實務專案使用官方推薦的密碼函式庫。）

13. C++ 範例檔案對照表

主題 檔案
Hash table + chaining + rehash cpp/hash_table_chaining.cpp
Linear / Quadratic / Double hashing + rehash cpp/hash_table_open_addressing.cpp
Division / Multiplication hash cpp/hash_functions_demo.cpp
字串多項式 hash cpp/polynomial_string_hash.cpp
Rabin-Karp cpp/rabin_karp.cpp
Prefix + double hash cpp/prefix_double_hash.cpp
Bloom filter cpp/bloom_filter.cpp
Consistent hashing + virtual nodes cpp/consistent_hashing.cpp
SHA-256 + PBKDF2（OpenSSL） cpp/openssl_crypto_demo.cpp

14. 編譯方式

在 Hash/cpp 目錄下：

g++ -std=c++17 -O2 -o hash_table_chaining hash_table_chaining.cpp
g++ -std=c++17 -O2 -o hash_table_open_addressing hash_table_open_addressing.cpp
g++ -std=c++17 -O2 -o hash_functions_demo hash_functions_demo.cpp
g++ -std=c++17 -O2 -o polynomial_string_hash polynomial_string_hash.cpp
g++ -std=c++17 -O2 -o rabin_karp rabin_karp.cpp
g++ -std=c++17 -O2 -o prefix_double_hash prefix_double_hash.cpp
g++ -std=c++17 -O2 -o bloom_filter bloom_filter.cpp
g++ -std=c++17 -O2 -o consistent_hashing consistent_hashing.cpp

OpenSSL 範例（需定義 HASH_ENABLE_OPENSSL=1 並連結 libcrypto，避免「有標頭卻連不到函式庫」的預設編譯失敗）。macOS Homebrew（Apple Silicon 常見路徑）：

g++ -std=c++17 -O2 -DHASH_ENABLE_OPENSSL=1 -o openssl_crypto_demo openssl_crypto_demo.cpp \
  -I/opt/homebrew/opt/openssl@3/include \
  -L/opt/homebrew/opt/openssl@3/lib \
  -lcrypto

未安裝或未連結 OpenSSL 時，仍可編譯出僅列印說明的執行檔：g++ -std=c++17 -O2 -o openssl_crypto_demo openssl_crypto_demo.cpp。

教材第 12 節仍完整涵蓋 MD5/SHA-1/SHA-256、bcrypt、PBKDF2 等概念（bcrypt 實務上多用函式庫綁定；範例以 PBKDF2 + SHA-256 示範「安全儲存形態」）。

教材版本：與目錄內 C++ 原始碼同步，供自主學習與面試複習使用。