學習資源

https://labuladong.online/algo/data-structure-basic/linear-probing-key-point/

學習記錄

今天是學習的第 14 天，主要學習了線性探查法的兩個難點：

線性探查法（開放尋址法）

與拉鏈法不同，線性探查法不使用額外的鏈表結構，而是直接在哈希表的陣列中尋找空位來解決衝突，相較於拉鏈表而言更複雜。

線性探查法基本原理

• 當哈希函式計算出的位置已被佔用時，順序向後查找下一個空位
• 所有鍵值對直接儲存在主陣列中，無需額外的鏈表結構
• 查找、插入、刪除操作都遵循相同的「向後探查」邏輯

兩大技術難點

難點一：需要環形陣列技巧

當向後探查到陣列末尾仍未找到空位時，需要回到陣列開頭繼續搜尋。

假設我們有一個大小為 7 的哈希表，使用簡單的取餘數作為哈希函式：hash(key) = key % 7

// 初始狀態：
table = [_, _, _, _, _, _, _]
index    0  1  2  3  4  5  6

// put(6, a)
// hash(6) = 6 % 7 = 6 
table = [_, _, _, _, _, _, a]
index    0  1  2  3  4  5  6

// put(13, b)
// hash(13) = 13 % 7 = 6（衝突！）
// 位置 6 已被佔用，向後探查發現已經是陣列末尾，回到陣列開頭 0 → 空位插入
table = [b, _, _, _, _, _, a]
index    0  1  2  3  4  5  6

難點二：刪除操作的複雜性

刪除操作必須維護元素的連續性，否則會破壞探查邏輯。主要有兩種解決方案：

1. 資料搬移法

   當 table 刪除元素時，將後面的元素往前移動，保證元素的連續性，但是只移動與被刪除元素同一哈希位置產生衝突的元素，舉個例子：

   假如刪除 key = 10 這個鍵值對，那後續就只移動 hash(10) = 0 的元素。

2. 占位符標記法

   通過一個特殊值作為佔位符來標記被刪除元素，可以避免資料搬移，同時保證元素的連續性。

拉鏈法和線性探查法的比較

學習總結

• 線性探查法有兩大技術難點
  1. 需要環形陣列技巧
  2. 刪除操作的複雜性
• 大部分程式語言實現的哈希表都是採用拉鏈法，因為更簡單且不易出錯