「給我一個字串，我立刻告訴你對應的值」——平均 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——

  1. 配置兩倍大的新桶陣列
  2. 走訪舊表每個項目，用新的桶數重算 hash % new_m，搬進新表
  3. 釋放舊桶陣列

注意：每個項目的桶號在擴容後幾乎都會變，所以必須逐項重算， 不能整桶搬移。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

常見錯誤與陷阱

  1. 只比雜湊值不比字串：碰撞的兩個鍵雜湊值相同，lookup 必須再 strcmp 確認，否則會拿到別人的值。
  2. hash 中的 char 符號性：*s 若是有號 char，負值參與運算會produce 意外結果；先轉 (unsigned char) 再運算。
  3. install 更新時的記憶體洩漏：鍵已存在時直接指過去新 defn， 舊的 defn 沒 free 就漏了；先 free 再替換。
  4. rehash 時沿用舊桶號：桶號依賴 % m，m 變了必須逐項重算， 照搬舊索引資料就找不到了。
  5. 把指標當鍵：lookup(p) 存的是指標而字串內容相同的另一個指標查不到； 鍵必須複製一份由表擁有（strdup），或明確約定生命週期。

練習題

  1. 【易】把 HASHSIZE 改成 1、10、1000 各跑一次 02_hashtable.c， 觀察桶分布與平均鏈長變化。
  2. 【易】為雜湊表加上 count（項目總數）與 foreach（走訪所有項目並套用回呼—— 複習函式指標）。
  3. 【中】實作 K&R 習題 6-5 的 undef（若你還沒讀範例解答）， 用指標的指標消除「刪頭」特例。
  4. 【中】做一個「單字頻率統計」：把上一單元的計數樹改成雜湊表版本， 比較兩者的程式碼複雜度與輸出順序差異。
  5. 【難】實作開放定址（open addressing）線性探測版本： 刪除要用墓碑（tombstone）標記，比較它與鏈結法的記憶體行為。
  6. 【難】寫一個碰撞攻擊示範：找出 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）