(開放定址法)
導讀
大家好，很高興又和大家見面啦！！！ 在上一篇內容中我們介紹了 處理衝突 的一種經典策略——拉鍊法：
- 通過 數組 + 鏈表 的組合，不僅有效的處理了衝突，還避免了堆積現象
雖然 拉鍊法 的優勢突出，但是 鏈表 同時也帶來了一些侷限性：
- 每一個結點都需要一個 額外的指針空間
今天我們將會介紹另一種 衝突處理策略 —— 開放定址法。我們會了解到，如何在不消耗 額外空間 的情況下，實現對 哈希衝突 的處理。下面就讓我們一起進入今天的主題；
一、基本概念
1.1 開放定址法
開放定址法，是指可存放新表項的空閒地址既向它的同義詞表項開放，又向它的非同義詞表項開放。其數學遞推公式為：
$$ H_i=(H(key)+d_i)%m $$
式中：
- $H(key)$ 是 哈希函數
- $i$ 可理解為“第 $i$ 次發生衝突”，且 $i=0,1,2,……,k(k \leq m-1)$
- $m$ 表示散列表表長；
- $d_i$為增量序列；
簡單的説，當我們通過 哈希函數 獲取的 哈希地址 中存在 關鍵字 時，就會發生 衝突 ，此時我們就可以考慮將 關鍵字 存放到其它 空閒地址； 如，我們通過 哈希函數 $Hash(key) = key \bmod 10$ 來存放數據 [1, 11, 2]：
- 首先我們通過 哈希函數 確認了 $key = 1$ 的 哈希地址 $Hash(key) = 1 \bmod 10 = 1$並將其進行存放：
此時由於表為一個 空表 ，因此 關鍵字 能夠直接存放：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 |
- 之後我們再一次通過 哈希函數 確認了 $key = 11$ 的 哈希地址：$Hash(key) = 11 \bmod 10 = 1$ 並將其進行存放：
不過由於該地址處已經存放了 $key = 1$ ，因此這兩個 關鍵字 就發生了 哈希衝突 ，此時我們就可以將其稱為 同義詞； 若我們要對 $key = 11$ 進行存放，我們就可以將其存放到其它還未存放關鍵字的地址中，如：
| 1 | $\textcolor{red}{2}$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 11 |
這裏我們直接將其存放到地址 $\textcolor{red}{2}$ 處；
- 最後我們再一次通過 哈希函數 確認了 $key = 2$ 的 哈希地址：$Hash(key) = 2 \bmod 10 = 2$ 並將其進行存放
若我們在存放 $key = 2$ 之前，未存放 $key = 11$ 那麼 $Hash(key) = 2$ 的位置處此時就是 空閒地址，因此我們可以直接將其存放到該地址處：
| 1 | $\textcolor{red}{2}$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 |
可以看到，不管是 $key = 2$ 還是 $key = 11$ 在 $Hash(key) = 2$ 為 空閒地址 時，均可以進行存放； 對於 $key = 1$ 而言，其 同義詞 $key = 11$ 可以存放到 $Hash(key) = 2$ 處，其 非同義詞 $key = 2$ 也可存放到 $Hash(key) = 2$ 處，因此我們稱 空閒地址 既向 同義詞 開放，又向 非同義詞 開放；
1.2 聚集與堆積
在 哈希表 中，存在着 聚集現象 與 堆積現象。這兩種現象均是指由於哈希衝突解決策略（特別是開放定址法）導致哈希表中出現連續被佔用的區塊，從而降低操作效率的情況。 下面我們將從4個維度來介紹這兩種現象：
-
二者關係
-
聚集現象 是一個 廣義 的概念，指的就是 形成連續被佔用區塊的趨勢；
-
堆積現象 則是 聚集現象 的一種 具體表現形式，通常特指由 非同義詞衝突 引發的 聚集
-
-
產生原因
-
聚集現象 是由 同義詞 或 非同義詞 爭奪後續 哈希地址 而產生的現象；
-
堆積現象 則是由 非同義詞 之間爭奪 同一個後續哈希地址 而產生的現象；
-
-
核心機制
-
聚集現象 的核心機制是因為 探測序列的規律性而導致的關鍵字在哈希表中扎堆；
-
堆積現象 的核心機制是因為 兩個關鍵字的探測序列相同而導致二者相互堵塞
-
-
包含關係
- 聚集現象 包含 一次聚集、二次聚集 等多種類型
- 堆積現象 則是通常被視為 二次聚集 的同義詞，或 二次聚集 的典型結果
1.2.1 實例演示
聚集現象 的核心特徵是：形成 連續 的被佔用單元區塊
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| true | true | true |
就如上表中，連續的單元區塊 1, 2, 3 被佔用，此時我們就可以成 1, 2, 3 發生了 聚集現象 堆積現象 的核心特徵是：形成了一條 很長的探測路徑
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $\cdots$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| true | true | true | true | $\cdots$ |
當兩個關鍵字的探測路徑均為：$（i + d_i)^2$ 時，就會發生 堆積現象
1.2.2 一次聚集與二次聚集
一次聚集 ：主要是由 線性探測法 引起。當發生衝突時，探測序列 是 固定步長（如依次檢查下一個位置）。這會導致同義詞以及被捲入的非同義詞在哈希表中原點附近形成一個大的連續佔用區塊，就像堵車時車輛在路口排起長隊。這是開放定址法中最常見也最需要避免的聚集類型 二次聚集：雖然採用了非固定步長的探測方法（如平方探測法），避免了“大區塊”式的一次聚集。但如果兩個不同的關鍵字（同義詞）的初始哈希地址相同，那麼它們接下來的整個 探測路徑 將完全一致。這導致這些 關鍵字 被“綁定”在同一條 探測路徑 上，雖然不會形成很大的連續區塊，但會使這條特定路徑變得很長，後續落入此地址的關鍵字探測成本會增高；
二、線性探測法
2.1 特點
線性探測法 也稱 線性探測再散列法，它是 開放定址法 處理衝突策略的最常見的一種方法。 在 線性探測法 中，$d_i=0,1,2,……,m-1$。該方法的特點是：
- 衝突發生時，順序查看錶中下一個單元，直到找出一個空閒單元或查遍全表。
即發生衝突時，每次往後探測相鄰的下一個單元是否為空：
- 若為空，則將 關鍵字 插入到該位置
- 若非空，則繼續往後查找：
- 當查找的位置為 $m - 1$ 時，則下一次查找會從 $0$ 位置處繼續查找
- 當表中未被填滿時，一定會存在一個空位供該關鍵字插入
- 當表中被填滿時，查找的過程會回到 $Hash(key)$ 處
2.2 插入
線性探測法 的 插入 過程並不難理解，可以分為兩步：
- 通過 哈希函數 獲取 哈希地址
- 判斷當前位置是否發生衝突：
- 發生衝突，繼續向後查找，並重復執行判斷
- 未發生衝突，插入 關鍵字
這裏我們通過具體的實例來説明整個 插入 的過程；
實例説明
現在我們需要對 [8, 10, 16, 20, 40, 50, 55, 60, 69, 77, 80, 85] 進行 哈希存儲，該 關鍵字序列 中有 $12$ 個元素，因此我們需要準備一個長度為 $L = 12$ 的數組作為 哈希表：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
由於該表長為 合適 因此我們選擇不大於表長的最大 質數 作為 除留餘數法 的 模數。滿足 $\leq 12$ 的最大 質數 為 $11$，因此對應的 哈希函數 為：
$$ Hash(key) = key \bmod 11 $$
接下來我們就可以通過該 哈希函數 進行 插入 操作了；
- 插入 $8$
關鍵字 $key = 8$ 對應的 哈希地址 為：$Hash(key) = 8 \bmod 11 = 8$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8 |
- 插入 $10$
關鍵字 $key = 10$ 對應的 哈希地址 為：$Hash(key) = 10 \bmod 11 = 10$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8 | 10 |
- 插入 $16$
關鍵字 $key = 16$ 對應的 哈希地址 為：$Hash(key) = 16 \bmod 11 = 5$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 16 | 8 | 10 |
- 插入 $20$
關鍵字 $key = 20$ 對應的 哈希地址 為：$Hash(key) = 20 \bmod 11 = 9$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 16 | 8 | 20 | 10 |
- 插入 $40$
關鍵字 $key = 40$ 對應的 哈希地址 為：$Hash(key) = 40 \bmod 11 = 7$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 16 | 40 | 8 | 20 | 10 |
- 插入 $50$
關鍵字 $key = 50$ 對應的 哈希地址 為：$Hash(key) = 50 \bmod 11 = 6$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 16 | 50 | 40 | 8 | 20 | 10 |
- 插入 $55$
關鍵字 $key = 55$ 對應的 哈希地址 為：$Hash(key) = 55 \bmod 11 = 0$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 55 | 16 | 50 | 40 | 8 | 20 | 10 |
- 插入 $60$
關鍵字 $key = 60$ 對應的 哈希地址 為：$Hash(key) = 60 \bmod 11 = 5$ ，通過查表可以看到，當前地址中已經存儲了 關鍵字 $key = 60$，因此我們需要通過 線性探測法 來處理該位置發生的 衝突：
$$ \begin{align*} H_i &= (H(key) + d_i) \bmod L \ H_0 &= (5 + 0) \bmod 12 = 5 \enspace {衝突} \ H_1 &= (5 + 1) \bmod 12 = 6 \enspace {衝突} \ H_2 &= (5 + 2) \bmod 12 = 7 \enspace {衝突} \ H_3 &= (5 + 3) \bmod 12 = 8 \enspace {衝突} \ H_4 &= (5 + 4) \bmod 12 = 9 \enspace {衝突} \ H_5 &= (5 + 5) \bmod 12 = 10 \enspace {衝突} \ H_6 &= (5 + 6) \bmod 12 = 11 \enspace {不衝突} \end{align*} $$
通過 線性探測法 我們發現，當出現 $6$ 次 衝突 後，我們在下標為 $11$ 的 空閒地址，因此我們需要將 $key = 60$ 插入到該地址處：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 55 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
- 插入 $69$
關鍵字 $key = 69$ 對應的 哈希地址 為：$Hash(key) = 69 \bmod 11 = 3$ ，通過查表可以看到，當前地址中沒有任何 關鍵字 ，因此可以直接插入：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 55 | 69 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
- 插入 $77$
關鍵字 $key = 77$ 對應的 哈希地址 為：$Hash(key) = 77 \bmod 11 = 0$ ，通過查表可以看到，當前地址中已經存儲了 關鍵字 $key = 77$，因此我們需要通過 線性探測法 來處理該位置發生的 衝突：
$$ \begin{align*} H_i &= (H(key) + d_i) \bmod L \ H_0 &= (0 + 0) \bmod 12 = 0 \enspace {衝突} \ H_1 &= (0 + 1) \bmod 12 = 1 \enspace {不衝突} \ \end{align*} $$
通過 線性探測法 我們發現，當出現 $1$ 次 衝突 後，我們在下標為 $1$ 的 空閒地址，因此我們需要將 $key = 77$ 插入到該地址處：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 55 | 77 | 69 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
- 插入 $80$
關鍵字 $key = 80$ 對應的 哈希地址 為：$Hash(key) = 80 \bmod 11 = 3$ ，通過查表可以看到，當前地址中已經存儲了 關鍵字 $key = 80$，因此我們需要通過 線性探測法 來處理該位置發生的 衝突：
$$ \begin{align*} H_i &= (H(key) + d_i) \bmod L \ H_0 &= (3 + 0) \bmod 12 = 3 \enspace {衝突} \ H_1 &= (3 + 1) \bmod 12 = 4 \enspace {不衝突} \ \end{align*} $$
通過 線性探測法 我們發現，當出現 $1$ 次 衝突 後，我們在下標為 $4$ 的 空閒地址，因此我們需要將 $key = 80$ 插入到該地址處：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 55 | 77 | 69 | 80 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
- 插入 $85$
關鍵字 $key = 85$ 對應的 哈希地址 為：$Hash(key) = 85 \bmod 11 = 8$ ，通過查表可以看到，當前地址中已經存儲了 關鍵字 $key = 85$，因此我們需要通過 線性探測法 來處理該位置發生的 衝突：
$$ \begin{align*} H_i &= (H(key) + d_i) \bmod L \ H_0 &= (8 + 0) \bmod 12 = 8 \enspace {衝突} \ H_1 &= (8 + 1) \bmod 12 = 9 \enspace {衝突} \ H_2 &= (8 + 2) \bmod 12 = 10 \enspace {衝突} \ H_3 &= (8 + 3) \bmod 12 = 11 \enspace {衝突} \ H_4 &= (8 + 4) \bmod 12 = 0 \enspace {衝突} \ H_5 &= (8 + 5) \bmod 12 = 1 \enspace {衝突} \ H_6 &= (8 + 6) \bmod 12 = 2 \enspace {不衝突} \ \end{align*} $$
通過 線性探測法 我們發現，當出現 $6$ 次 衝突 後，我們在下標為 $2$ 的 空閒地址，因此我們需要將 $key = 85$ 插入到該地址處：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 55 | 77 | 85 | 69 | 80 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
此時我們就完成了全部的插入過程。這裏需要注意的是，因為我們是希望將元素插入到整個表中，因此這裏我們使用的 $m$ 不是 哈希函數 中使用的 質數 ，而是 實際表長；
2.3 查找
當我們對 哈希表 進行查找時，我們需要執行兩步：
- 通過 散列函數 計算 散列地址
- 通過 關鍵字 對比進行 順序查找
- 遇到空時，查找失敗
- 回到 散列地址 時，查找失敗
- 找到 目標關鍵字 時，查找成功
也就是説，當 哈希表 中發生了 衝突 後，通過 線性探測法 處理衝突後，我們在進行查找的過程與 拉鍊法 一致，都是需要通過 順序查找 完成； 不過對於查找失敗時的判斷，二者之間存在區別：
- 拉鍊法：查找到 空指針 時，查找失敗
- 哈希地址 對應的 鏈表 為 空鏈表
- 對 鏈表 完成了查找，找到了最後的 空指針
- 線性探測法：根據 哈希表 的存儲情況進行具體的判斷：
- 哈希表 已存滿，則從 哈希地址 出發向後順序查找，最後回到 哈希地址
- 哈希表 未存滿，則從 哈希地址 出發向後順序查找，找到了 空閒地址
這裏可能有朋友會有疑問——為什麼 哈希表 未存滿時，找到了 空閒地址 就代表 查找失敗？ 這個問題其實很容易理解： 若我們需要在表中 插入 這個 關鍵字 那麼此時找到的 空閒地址 就應該是該 關鍵字 插入的地址，因此當我們找到了這麼一個 空閒地址 時，就表示 哈希表 中不存在該元素；
2.4 刪除
當我們對使用了 開放定址法 處理衝突策略的 哈希表 進行 刪除 操作時，我們不能向使用了 拉鍊法 的 哈希表 一樣直接將 目標關鍵字 刪除； 這是由於其 查找 操作的不同：
- 使用 拉鍊法 處理衝突的 哈希表 ，其 查找 操作實際上就是對 鏈表 進行查找
- 使用 開放定址法 處理衝突的 哈希表 ，其 查找 操作實際上就是對 循環數組 進行查找
正是因為這二者的性質不同，這就導致了其 查找失敗 的條件也有區別：
- 拉鍊法：
- 鏈表 為空表時，查找失敗
- 鏈表 中所有元素都被查找，仍為查找到 目標 時，查找失敗
- 開放定址法
- 循環數組 被填滿時，從起始點開始查找，最後回到起始點時，查找失敗
- 循環數組 未被填滿時，遇到 空閒地址時，查找失敗
因此，若我們在使用了 開放定址法 的 哈希表 中直接刪除元素，就會導致一個問題：
- 若 目標關鍵字 位於已刪除的 關鍵字 後面，則我們無法通過 查找 操作找到目標關鍵字
這裏我們以前面的例子進行説明，就比如我們要刪除 $key = 55$ ，完成刪除後，我們就得到了下表：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 刪除前 | 55 | 77 | 85 | 69 | 80 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
| 刪除後 | 77 | 85 | 69 | 80 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
之後我們還要刪除 $key = 77$ ，通過 哈希函數 我們可以得到該 關鍵字 的 哈希地址 為：$Hash(key) = 77 \bmod 11 = 0$ ； 由於此時該地址處為 空閒地址，根據其 查找 機制，我們就會得到一個結論——該表中沒有 $key = 77$； 顯然這個結論是錯誤的，因此為了避免出現這種問題，我們在對使用了 開放定址法 處理衝突策略的 哈希表 進行刪除時，我們只能夠採用 邏輯刪除：
- 通過一個 刪除標誌 來標記已被 邏輯刪除 的元素，而不直接進行 物理刪除
這裏我們還是採用剛才的例子，就比如我現在要刪除 $key = 55$ ，那麼我們可以通過一個 標記數組 來記錄該元素的狀態：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 關鍵字 | 55 | 77 | 85 | 69 | 80 | 16 | 50 | 40 | 8 | 20 | 10 | 60 |
| 標記數組<br>刪除前 | $\textcolor{red}{false}$ | false | false | false | false | false | false | false | false | false | false | false |
| 標記數組<br>刪除後 | $\textcolor{red}{true}$ | false | false | false | false | false | false | false | false | false | false | false |
此時，若我們需要繼續刪除 $key = 77$ ，那麼我們根據 哈希函數 獲取的 哈希地址 $Hash(key) = 77 \bmod 11 = 0$ 進行查找時，此時該位置已經存在 關鍵字 $key = 55$ ，因此接下來我們會繼續向後進行 查找；
2.5 查找效率
由於 線性探測法 是在發生衝突時，依次往後尋找 空閒地址，這就導致了其最壞情況下 哈希表 會退化為 數組，即查找效率從 $O(1)$ 退化到了 $O(N)$； 這是因為在最壞情況下，每一次的插入都會發生 衝突，而通過 線性探測法 處理衝突時：
- 衝突後再探測，關鍵字 一定是放在某個連續的位置
這就導致了 線性探測法 很容易造成同義詞與非同義詞的 聚集現象，嚴重影響查找效率。 因此通過 線性探測法 處理 哈希衝突 的 哈希表 ，其查找效率低下。
結語
在今天的內容中我們介紹了詳細介紹了 開放定址法 的基本概念：
- 可存放新表項的空閒地址既向它的同義詞表項開放，又向它的非同義詞表項開放
瞭解了 聚集 與 堆積 這兩種現象：
- 聚集現象 是指 形成連續被佔用區塊的趨勢
- 堆積現象 是 聚集現象 的一種 具體表現形式
最後深入探討了 線性探測法：
- 衝突發生時，順序查看錶中下一個單元，直到找出一個空閒單元或查遍全表
正是由於 線性探測法 的 固定步長探測序列 ，使得 同義詞 與 非同義詞 在 哈希表 中形成了一個很大的 連續佔用區塊，這就導致了 聚集現象 的發生，從而嚴重降低了 哈希表 的查找效率； 在下一篇內容中，我們將會了解第二種 開放定址法 —— 平方探測法。相比於 線性探測法 ，平方探測法 又是如何處理 哈希衝突 的呢？這個問題的答案，咱們將在下一篇內容中進行揭曉； 互動與分享
-
點贊👍 - 您的認可是我持續創作的最大動力
-
收藏⭐ - 方便隨時回顧這些重要的基礎概念
-
轉發↗️ - 分享給更多可能需要的朋友
-
評論💬 - 歡迎留下您的寶貴意見或想討論的話題
感謝您的耐心閲讀！ 關注博主，不錯過更多技術乾貨。我們下一篇再見！
