1.2 Hash table 與 collision 策略

從 dictionary 查詢選擇儲存方式

Dictionary 把每個 key 對應到一個 value。若以未排序的 list 儲存，搜尋可能 需要檢查每個 entry；若保持陣列有序，可以使用 binary search，但插入新 key 時可能需要移動大量 entry。直接以 key 作為陣列索引可以省去搜尋，卻要求 key 屬於合適的整數範圍；任意字串並不提供這樣的索引。

Hash table 從 key 計算 index，只搜尋分配到該位置的候選項。它不維持排序 關係，以減少 lookup 與 update 的期望工作量。不過，有限 index 無法區分 所有可能的 key，因此即使發生 collision，表示方式仍須保留各個不同 entry。

Dictionary 契約

以 opaque pointer 表示 value

下面的 C interface 以 void * 表示 value，使介面不依賴 value 的具體型別。

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 決定。

從 key 計算合法 index

合適的 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;
}

不同 key 為何會共用 bucket

若 key 的取值範圍包含的 key 多於 bucket 數量，就至少有兩個可能的 key 對應同一 index。這並不表示每個小規模輸入已經發生 collision，而是表示 任何映射到該有限範圍的 hash function 都無法對所有合法輸入排除 collision。 Hashing 只確定候選項，仍須比較 key，才能確認某個候選項正是查詢目標。

Chaining 把 collision 的 entry 存入 bucket 所連接的 list；open addressing 則把它們存入同一個 table 的其他 slot，並透過可重複的 probe sequence 找回。 兩者都必須找到 key 相同的 entry，不能直接採用遇到的第一個非空位置。

Chaining：以鏈結保存同 bucket 的 entry

Chaining 把碰撞的 entry 存在 bucket 所連接的 linked list。

Bucket chain 使用的仍是 pointer 連接的 node：

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

因此 lookup 可以分成兩層：

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

Bucket 內的次序不屬於 dictionary 契約。實作可以在鏈首、鏈尾或按其他一致 規則插入，只要 lookup 與 overwrite 仍能找到正確的 key。這個選擇改變的是 表示方式，不是 key-value 對應的意義。

Occupancy 與期望搜尋成本

即使 hash function 的分布合適，table 的 occupancy 仍會影響搜尋成本。

設 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 也是維持 hash table 預期效能的必要考量。

Open addressing：在同一 table 內 probing

Open addressing 把 entry 存在 table 內；首選 slot 已被佔用時，便按 probe rule 繼續檢查其他位置。

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

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

Linear probing 容易形成連續的 filled buckets，稱為 primary clustering。 Cluster 越長，後續 probe 越容易進入同一段密集區域，搜尋成本也隨之增加。

Quadratic probing 以不同的 offset 減少 primary clustering。

設 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 必須一併設計。

Deletion 還必須保留搜尋路徑，讓其後插入到同一 probe sequence 的 entry 仍然可達。直接把刪除位置標成從未使用的空位，可能中斷這條路徑。這裏的 probe 例子討論 insertion 與 lookup，沒有訂明 deletion 的具體實作。

Bucket 數量改變後需要 rehash

Bucket 數量參與 index 的計算。即使底層 hash code 不變，改變 bucket 數量 也可能把已有 entry 分配到新位置。因此，每個 entry 都須按新規則重新放置； 這個過程稱為 rehashing。

Collision 策略的取捨

不同方案適合不同條件，選擇時須比較各自的 tradeoff。

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

選擇取決於 table size、預期 load、記憶體佈局及 update pattern。Probe rule 必須先滿足 coverage 條件，才有比較其速度的意義。

常見錯誤

總結

Dictionary 契約規定每個 key 對應的 value，表示方式則決定這個關聯存在哪裏。 Hashing 選擇候選項，key comparison 確認目標，collision handling 保持每個 已存 key 可達。期望效率依賴 key/hash 的模型與 occupancy；改變表的大小後， 必須透過 rehashing 使存放位置與 lookup 使用的規則繼續一致。

快速檢查

練習