1.2 Hash table 與 collision 策略

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

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

仍然要先由 ADT 角度開始

Hashtable tutorial 仍然先由操作出發，而唔係先由 bucket 出發：

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

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

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

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

Hash function 應該做乜

本地 tutorial 特別強調一個好 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 正確」。

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

Lecture material 用 chaining 作為最直觀的補救方法。

呢個做法同上一節的 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

Tutorial 亦介紹 open addressing。呢種方法唔係喺 bucket 下面掛 linked list， 而係當首選 slot 被佔用時，繼續去 table 內其他位置 probing。

常見 probing 方式包括：

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

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

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

所以 deletion、clustering 同 probe sequence 設計就變得非常重要。

Load factor 點解重要

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

Load factor 通常寫成

當 $\alpha$ 上升時：

• chaining 的鏈會變長；
• open addressing 的 probe sequence 會變長；
• 平均情況下的 lookup 會慢慢偏離理想的常數時間。

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

Generic pointer 令 ADT 可重用

本地 hashtable lecture 用 $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

Lecture 其實唔係先講 bucket，而係先講 ADT contract。呢個次序好重要，因為 hash table 首先係 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

Tutorial 同 lecture 都有講 open addressing。呢種方法唔係喺 bucket 底下掛 linked list，而係當首選 slot 已經被佔用時，繼續喺 table 入面搵下一個位置。

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

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

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

Quadratic probing 就係針對呢個問題。

呢個就係 CSCI2520 好典型的 tradeoff：規則更精細，可以換來更好的分散；但 實作亦會更複雜。

Rehashing 係改 table 形狀的代價

當 bucket 數目改變，hash function 都要跟住改。原本已經存入去的 entry，就要 用新 rule 再入一次。呢個過程叫 rehashing。

Lecture 亦提醒過，rehashing 對大多數應用來講其實唔算常常發生，但概念上一定 要理解，因為佢說明咗 hash table 並唔係一個固定唔變的 memory picture。

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

Source material 唔係叫你揀一個「永遠最好」的方案，而係叫你睇明 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 時先問呢幾件事

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

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

更多練習