申論題

連結串列法（Chaining）

定義： 連結串列法是一種處理雜湊表中碰撞（collisions）的方法。當兩個或多個鍵值經過雜湊函數運算後映射到相同的桶（bucket）時，將這些鍵值存儲在一個連結串列（linked list）中。

運作原理：

1. 雜湊：
   • 將每個鍵值經過雜湊函數運算，得到桶的索引值。
2. 存儲：
   • 如果該桶是空的，則將該鍵值存入桶中。
   • 如果該桶中已經有其他鍵值，則將新鍵值添加到該桶對應的連結串列中。
3. 查找：
   • 將查找鍵值經過雜湊函數運算，找到對應的桶。
   • 遍歷桶中的連結串列，查找對應的鍵值。

優點：

• 解決碰撞：有效處理鍵值碰撞問題，避免槽位直接填滿。
• 動態調整：桶內的連結串列可以動態增長，沒有固定大小的限制。

缺點：

• 額外存儲開銷：需要額外的存儲空間來存儲連結串列中的指針。
• 查找效率：在最壞情況下（所有鍵值都映射到同一個桶），查找效率會降低到 O(n)。

圖示範例：

假設有以下鍵值：15, 11, 27, 8, 12，使用雜湊函數 ℎ(?)=?mod  5h(k)=kmod5 並使用連結串列法處理碰撞。

1. 鍵值 15：

   • ℎ(15)=15mod  5=0h(15)=15mod5=0
   • 插入位置0：0:150:15

2. 鍵值 11：

   • ℎ(11)=11mod  5=1h(11)=11mod5=1
   • 插入位置1：1:111:11

3. 鍵值 27：

   • ℎ(27)=27mod  5=2h(27)=27mod5=2
   • 插入位置2：2:272:27

4. 鍵值 8：

   • ℎ(8)=8mod  5=3h(8)=8mod5=3
   • 插入位置3：3:83:8

5. 鍵值 12：

   • ℎ(12)=12mod  5=2h(12)=12mod5=2
   • 插入位置2（碰撞，添加到連結串列）：2:27−>122:27−>12

連結串列法有效地解決了碰撞問題，允許在同一個桶中存儲多個鍵值，使得雜湊表能夠處理更多的數據。