「給我一個字串，我立刻告訴你對應的值」——平均 O(1) 的查找就是雜湊表的魔法。
編譯器的符號表、shell 的環境變數、Python 的 dict、資料庫的索引快取，
底層都是它。本單元對應 K&R §6.6 的表格查詢（table lookup）範例，
實作 hash/lookup/install/undef 全套，並補充 djb2 雜湊、負載因子與 rehash。
學習目標
- 理解雜湊表的核心思想：雜湊函式 + 桶陣列 + 碰撞處理
- 會實作與評估字串雜湊函式（K&R hash、djb2）
- 用鏈結法（separate chaining）處理碰撞
- 完整實作 K&R §6.6 的
lookup/install/undef - 理解負載因子（load factor）與 rehash 擴容
- 能用雜湊表解「字串 → 值」的字典類問題
對照章節 / 參考來源
- K&R §6.6 Table Lookup（
#define名值對的符號表） - CLRS 第 11 章 Hash Tables
- Daniel J. Bernstein 的 djb2 雜湊（comp.lang.c 貼文）
- SipHash 論文（現代抗碰撞攻擊的雜湊，延伸）
觀念講解
1. 整體結構
hash("format") = 3
│
桶陣列 v
┌────┬────┬────┬────┬────┬────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ ...（HASHSIZE 個桶）
└─┬──┴────┴────┴─┬──┴────┴────┘
│ │
v v
["max"|"100"] ["format"|"%d"] ──> ["fmt"|"%s"] ──> NULL
│ （碰撞的項目串成鏈結串列）
v
NULL三步驟：hash(key) 算出桶號 → 走訪該桶的串列 → strcmp 精確比對。
雜湊值只負責「分桶」，同桶內仍要逐一比字串——因為不同字串可能有相同雜湊值（碰撞）。
2. 雜湊函式
K&R §6.6 的版本（簡單夠用）：
unsigned hash(const char *s)
{
unsigned h;
for (h = 0; *s != '\0'; s++)
h = *s + 31 * h;
return h % HASHSIZE;
}djb2（Daniel J. Bernstein，實務上最常被抄的版本）：
unsigned long djb2(const char *s)
{
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++))
h = ((h << 5) + h) + c; /* h * 33 + c */
return h;
}好的雜湊函式要「快」且「散得均勻」。31、33 這類小質數乘子讓每個字元 都影響高低位；差一個字元的字串（"ab" vs "ac"）雜湊值就大不相同。 評估方法：對一批真實鍵值統計每桶長度的分布（範例程式會做這件事）。
3. K&R lookup / install / undef
K&R 用雜湊表實作 #define 的名值對表格：
struct nlist { /* 表項：名稱-定義對 */
struct nlist *next; /* 同桶的下一項 */
char *name;
char *defn;
};
struct nlist *lookup(const char *s); /* 找到回傳項目，否則 NULL */
struct nlist *install(const char *name, const char *defn); /* 新增或更新 */
int undef(const char *name); /* 刪除（K&R 習題 6-5） */install 的邏輯：先 lookup——已存在就換掉 defn（free 舊的），
不存在就建新節點頭插進對應的桶。undef 就是上一單元的串列刪除，
用指標的指標寫最乾淨。
4. 負載因子與 rehash
負載因子 α = 項目數 n / 桶數 m。鏈結法的平均查找長度約 1 + α/2， α 太大時退化成串列搜尋。策略：α 超過門檻（常見 0.75 ~ 1.0）就 rehash——
- 配置兩倍大的新桶陣列
- 走訪舊表每個項目，用新的桶數重算
hash % new_m，搬進新表 - 釋放舊桶陣列
注意：每個項目的桶號在擴容後幾乎都會變，所以必須逐項重算， 不能整桶搬移。rehash 單次 O(n)，攤銷到每次插入仍是 O(1)。
5. 複雜度
| 操作 | 平均 | 最壞（全碰撞） |
|---|---|---|
| lookup | O(1) | O(n) |
| install | O(1) | O(n) |
| undef | O(1) | O(n) |
| rehash | — | O(n)（攤銷 O(1)/插入） |
最壞情況在對抗性輸入（攻擊者故意製造碰撞）下會發生—— 這就是 DoS 攻擊 "hash flooding"，現代語言 runtime 改用帶隨機種子的 SipHash 防禦。
6. 選型：雜湊表 vs BST
| 雜湊表 | BST（平衡） | |
|---|---|---|
| 查找/插入 | 平均 O(1) | O(log n) |
| 有序走訪 | 不支援（順序打散） | 中序即排序 |
| 範圍查詢 | 不支援 | 支援 |
| 最壞情況 | O(n)（碰撞） | O(log n) 有保證 |
要「最快的等值查找」用雜湊表；要「排序、範圍、前綴」用樹。
範例程式
| 檔案 | 內容 | 編譯 / 執行 |
|---|---|---|
01_hash_functions.c |
K&R hash 與 djb2 的實作、雪崩效應觀察、桶分布統計比較 | cc -std=c11 -Wall -Wextra -o out 01_hash_functions.c && ./out |
02_hashtable.c |
K&R lookup/install/undef 全套 + 走訪 + 統計 + 完整釋放 | cc -std=c11 -Wall -Wextra -o out 02_hashtable.c && ./out |
03_rehash.c |
帶負載因子監測與自動 rehash 的動態雜湊表（字串→int 字典） | cc -std=c11 -Wall -Wextra -o out 03_rehash.c && ./out |
常見錯誤與陷阱
- 只比雜湊值不比字串：碰撞的兩個鍵雜湊值相同，
lookup必須再strcmp確認，否則會拿到別人的值。 hash中的 char 符號性：*s若是有號 char，負值參與運算會produce 意外結果；先轉(unsigned char)再運算。- install 更新時的記憶體洩漏：鍵已存在時直接指過去新 defn， 舊的 defn 沒 free 就漏了；先 free 再替換。
- rehash 時沿用舊桶號：桶號依賴
% m，m 變了必須逐項重算， 照搬舊索引資料就找不到了。 - 把指標當鍵：
lookup(p)存的是指標而字串內容相同的另一個指標查不到； 鍵必須複製一份由表擁有（strdup），或明確約定生命週期。
練習題
- 【易】把
HASHSIZE改成 1、10、1000 各跑一次02_hashtable.c， 觀察桶分布與平均鏈長變化。 - 【易】為雜湊表加上
count（項目總數）與foreach（走訪所有項目並套用回呼—— 複習函式指標）。 - 【中】實作 K&R 習題 6-5 的
undef（若你還沒讀範例解答）， 用指標的指標消除「刪頭」特例。 - 【中】做一個「單字頻率統計」：把上一單元的計數樹改成雜湊表版本， 比較兩者的程式碼複雜度與輸出順序差異。
- 【難】實作開放定址（open addressing）線性探測版本： 刪除要用墓碑（tombstone）標記，比較它與鏈結法的記憶體行為。
- 【難】寫一個碰撞攻擊示範：找出 20 個在
HASHSIZE=101的 K&R hash 下 同桶的字串，量測 lookup 退化的程度。
補充：雜湊表無所不在
- 編譯器符號表：K&R 這個範例的本尊——
#define與變數名的查找。 - shell 與直譯器：環境變數、Python dict、JavaScript object、 Lua table，語言核心資料結構就是雜湊表。
- 快取：memcached / Redis 的主索引、CPU 分支預測器的歷史表。
- 去重與計數：日誌分析「每個 IP 出現幾次」一行雜湊表解決。
- inode cache / dentry cache：作業系統核心用雜湊表加速路徑查找。
一句話總結選型：不需要順序就用雜湊表；需要排序/範圍查詢才考慮樹。
延伸閱讀
- K&R §6.6 與習題 6-5、6-6
- CLRS 第 11 章（含全域雜湊 universal hashing）
- djb2 與 FNV-1a：兩個最常見的簡易字串雜湊
- SipHash: a fast short-input PRF（Aumasson & Bernstein）
- Python dict 的實作演進（open addressing + perturbation）