1.2 Hash table 與 collision 策略

當 ADT、pointer 同基本 node 結構已經建立好之後，下一個問題就係：如何高效 支援 dictionary 類操作？Hash table 係其中一個標準答案。佢唔保留排序結構， 而係先用 hash function 將 key 跳到某個 bucket。

呢個跳轉好有力，但永遠唔會完美。整章內容都係用嚟解釋：呢個跳轉可以保證 乜嘢、collision 點樣出現，以及當多個 key 撞入同一位置時，實作點樣補救。

動機

先列出 hash table 需要支援的 dictionary 操作：

• 為某個 key 插入 value；
• 按 key 找返 value；
• 刪除已存在嘅 key-value entry。

所以邏輯對象首先係 dictionary 或 symbol table。Hash table 只係實作呢個 ADT 的其中一種方法。

呢個定義已經暗示兩條設計線：

• key 點樣被轉成 bucket index；
• 如果兩個 key 去到同一個 index，實作會點做。

Hash function 應該做乜

一個好 hash function 應具備四點：

• 永遠回傳合法 bucket index；
• 盡量減少 collision；
• 盡量平均分散 key；
• 計算本身要夠快。

最後一點唔可以忽略，因為如果 hash 規則本身太慢，就算分散效果好，lookup 都未必值得。

int Hash(char *s, int nBuckets) {
   int h = 0;
   while (*s != '\0') {
      h += *s;
      s++;
   }
   return h % nBuckets;
}

Collision 不是例外，而是常態

只要 bucket 數量有限，而 key 空間夠大，collision 就幾乎無可避免。所以 真正要問的唔係「如何完全避免 collision」，而係「有 collision 時仍然如何 保持 dictionary 正確」。

觀看 collision handling 如何保持 dictionary 正確

下面的短圖解會保留 ADT contract，同時比較兩種主要補救方式。Hashing 只決定由邊度開始搜尋；chaining 同 probing 則解釋 table 如何在 collision 之後仍不混淆不同 key。

Chaining：同一個 bucket 下面掛一條鏈

Chaining 將碰撞的 entry 保留喺 bucket 旁邊的 linked list。

呢個做法同上一節的 pointer / node 模型完全配合：

typedef struct cellT {
   char *key;
   void *value;
   struct cellT *next;
} cellT;

因此 lookup 可以分成兩層：

1. 先 hash key，選出 bucket；
2. 再只掃描該 bucket 底下的 linked list。

Open addressing：唔用鏈，而係繼續 probing

Open addressing 將所有 entry 留喺 table 內。呢種方法唔係喺 bucket 下面掛 linked list， 而係當首選 slot 被佔用時，繼續去 table 內其他位置 probing。

常見 probing 方式包括：

• linear probing；
• quadratic probing；
• double hashing。

同 chaining 最大分別係：額外工作喺邊度發生。

• chaining 將 collision 放去 bucket side 的 linked structure；
• open addressing 將 collision 變成 table 內部的續搜。

所以 clustering 同 probe sequence 設計就變得非常重要。Deletion 另外需要規則 去保留 probe path；本節將 delete 列為 ADT 操作，但唔展開呢個獨立 invariant。

Load factor 點解重要

即使 hash function 本身唔差，只要 table 太滿，效能都會變壞。

設 table 有 n 個 entry、m 個 bucket，load factor 通常寫成

對 chaining 來講，n 可以大過 m，所以 $\alpha$ 可以大過 1。對 open addressing 來講，每個 slot 最多存一個 live entry，因此 $0 \le \alpha \le 1$；要插入新的 key，除咗要有 $\alpha < 1$，probe sequence 亦必須真係去得到空 slot。

定理 / 命題

證明思路

喺 chaining 入面，各條 bucket chain 將 n 個 entry 分開：每個 entry 恰好屬於 一條 chain。因此，將所有 chain length 相加會將每個 entry 計一次，得到 $\sum_j\ell_j=n$；再除以 m，就得到平均 occupancy $\alpha$。

呢個係確定性的計數恆等式，本身並唔保證 lookup 係常數時間。要得到 $O(1+\alpha)$ 呢類期望界，仲需要合適的 hash function 或 key distribution 假設。冇呢個假設時，即使 load factor 好細，仍然可以出現一條好長的 chain。

當 table 的 load 增加時：

• chaining 的平均 chain length 嚴格等於 $\alpha$，但每條 chain 的實際長度 取決於 key 的分布；
• 當 $\alpha$ 接近 1 時，open addressing 的 probe sequence 通常會變長， 而且仍然要滿足 probe coverage 條件；
• 如果分布或者 load 冇受到控制，平均 lookup 會偏離理想的常數時間。

所以 resize 唔只係工程細節，亦係保護 hashtable 效能模型的一部分。

Generic pointer 令 ADT 可重用

下面的 C interface 用 void * 去表示 value，呢個其實係 ADT 的重要 設計選擇。

typedef struct hashtableCDT *hashtableADT;

hashtableADT EmptyHashtable();
void Enter(hashtableADT table, char *key, void *value);
void *Lookup(hashtableADT table, char *key);

Table 本身唔需要知道 value 的具體型別。它只需要維持 key 與某個 opaque pointer 之間的關聯，而真正如何解讀那個 pointer，則由 client 決定。

常見錯誤

快速檢查

練習

更仔細咁讀 implementation

讀 implementation 時，先明確 ADT contract，再檢查 bucket 佈局。Contract 規定咗每種存放方式都必須實現的 dictionary 操作。

呢個 overwrite 行為好容易忽略，但正正就係點解呢個 ADT 係 dictionary， 而唔係 multiset。

Hashing 之後點解仍然要比較 key

Hashing 只係縮窄搜尋範圍，唔係完成搜尋。呢點係 collision 理論入面最核心 嘅直覺之一。

如果兩個 key 落咗同一個 bucket，table 仍然要比較儲存入面嘅 key 同查詢 key 係咪真係一樣。否則就分唔到係真正命中，定係只係碰巧撞到同一個 bucket。

Chaining 的好處係 collision structure 分開存

最直觀的 collision strategy 就係 chaining。每個 bucket 指向一條 linked list， 而所有 hash 去同一個 bucket 的 entry 都掛喺同一條 chain 上。

呢個做法有一個實際好處：chain 入面嘅順序唔係 dictionary contract 的一部分。 你可以將新 entry 放前、放後，甚至按其他一致規則插入，只要 lookup 同 overwrite 行為正確，ADT 就仍然成立。

Open addressing：唔掛鏈，而係繼續 probing

Open addressing 唔係喺 bucket 底下掛 linked list，而係當首選 slot 已經被 佔用時，繼續喺 table 入面搵下一個位置。

Collision 的成本因此轉移到 probing rule 本身。

• linear probing 會檢查下一格，再下一格，一路向前；
• quadratic probing 會跳平方步；
• double hashing 會用第二個 hash function 產生 step size。

Linear probing 容易形成一長串連續 filled buckets，呢種現象 叫 primary clustering。cluster 一長，之後 probe 就更容易撞到同一段區域，效能會 慢慢跌落去。

Quadratic probing 就係針對呢個問題。

設 table size 為 10、h(k) = k % 10，第二個 hash 為 $s(k)=7-(k\bmod 7)$。對 key 23，step 為 $s(23)=7-(23\bmod 7)=5$。由 bucket 3 開始時，因為 $\gcd(5,10)=5$，probe 只會喺 3 同 8 之間循環；如果兩格都已經被佔用， 佢就去唔到其他空 slot。合適的第二個 hash 可以令 probe 分布更好，但 table size 同 step rule 必須一齊設計。

Rehashing 係改 table 形狀的代價

當 bucket 數目改變，由 hash code 縮減到 bucket index 的規則亦會改變。 即使底層 hash-code computation 保持不變，原本已經存入去的 entry 仍然要按新的 bucket rule 重新放置。呢個過程叫 rehashing。

喺固定容量的實作入面，rehashing 可能唔常發生；但概念上一定要理解， 因為佢說明會增長的 hash table 並唔係一個固定唔變的 memory picture。

點樣揀 chaining、linear probing、quadratic probing、double hashing

冇一個方案永遠最好；選擇時需要比較各自的 tradeoff。

• Chaining 容易理解，而且用 linked list 就可以處理 collision。
• Linear probing 簡單，但容易出現 primary clustering。
• Quadratic probing 可以減少 clustering，但對 load factor 更敏感。
• Double hashing 通常 probe 分散得更好，但因為要第二個 hash function，所以更 貴、更複雜。

如果你喺讀 C code，最安全的問題唔係「理論上邊個最快？」而係「呢個 table 的 size、load、同 update pattern，究竟同邊種策略最夾？」

總結

讀 code 時，可以先用下面呢份簡短 checklist：

1. key 係咩，value 係咩？
2. Enter 遇到已存在的 key 時會點？
3. lookup 之後有冇再比較 stored key？
4. collision 係由 chain 處理，定 probe sequence 處理，抑或兩者都有？
5. table 太滿時會發生咩事？

如果呢五個答案清楚，hash table implementation 就會容易得多。

更多練習