(開放定址法)
導讀
大家好，很高興又和大家見面啦！！！ 通過前面的內容，我們已經學習了兩種 開放定址法 ：
- 線性探測法：通過 固定探測步長 處理衝突
- 平方探測法：通過 平方跳躍步長 處理衝突
但是這兩種方法均會帶來一定的問題：
- 線性探測法 會導致 一次聚集 的現象
- 平方探測法 會導致 二次聚集 的現象
因此，在 開放定址法 中是否存在着能夠避免這種 聚集現象 的衝突處理方法呢？ 答案是肯定的，這就是我們今天要介紹的 偽隨機數法 以及 雙散列法。 接下來就讓我們一起深入探討一下這兩種方法是如何做到在處理衝突的同時還能夠避免 聚集現象；
一、偽隨機序列法
偽隨機序列法 指的是人為的設置一個 偽隨機序列 $d_i$ ，如
$$ d_i=0,5,24,11,…… $$
當發生衝突時，按照 偽隨機序列 去進行 循環探測 ，直到找到 空閒地址； 熟悉 C 語言的小夥伴應該都知道，在 C 的標準庫中存在着一個 偽隨機函數 —— rand() ，它的作用就是生成一個 偽隨機數，因此我們如果想要通過 偽隨機序列法 來處理衝突，我們就可以藉助該函數來生成 偽隨機序列；
#include <stdlib.h>
int Get_Random(){
return rand() % 100; // 生成0 ~ 99 的偽隨機數
}
1.1 優勢
偽隨機序列法 相對於 線性探測法 以及 平方探測法 ，它通過 偽隨機數生成器 生成的 偽隨機探測序列 $d_i$ ，能夠有效的降低因 固定步長探測序列 導致的 一次聚集 以及 相同的探測序列 導致的 二次聚集 ，使得數據在 哈希表 中分佈的更加均勻；
1.2 侷限
偽隨機序列法 的侷限性主要體現在兩個方面：
-
計算成本：由於 偽隨機序列法 的每一次探測都需要通過 偽隨機數生成器 生成一個 偽隨機數 ，相比於 線性探測法 以及 平方探測法 ，它在無形之中就增加了 時間開銷
-
高度依賴偽隨機序列：當 偽隨機數生成器 生成的 偽隨機序列 的質量低下時，如生成的序列類似於 線性探測法 的 固定步長探測序列，或者生成的序列類似於 平方探測法 的 平方跳躍探測序列，這就會導致 一次聚集 或者 二次聚集 的概率直線增加。
當然，於 線性探測法 以及 平方探測法 一樣，偽隨機序列法 同樣只能夠進行 邏輯刪除；
二、雙散列法
雙散列法 是指使用兩個 哈希函數 ，當通過第一個 哈希函數 $Hash_1(key)$ 得到的 哈希地址 發生衝突時，再利用第二個 哈希函數 $Hash_2(key)$ 計算該關鍵字的 地址增量 （或者説 探測序列）$d_i$。 雙散列法 的 哈希函數 形式為：
$$ H_i = (Hash_1(key) + i * Hash_2(key)) \bmod m $$
2.1 哈希函數的設計
在 雙散列法 中，我們需要準備兩個 哈希函數：
$$ \begin{align*} Hash_1(key) &= key \bmod m \ Hash_2(key) &= 1 + (key \bmod (m - 1)) \ {或} \enspace Hash_2(key) &= R - (key \bmod R) \end{align*} $$
對於第一個 哈希函數 我們可以按照前面介紹的 $4$ 種方法進行設計：
- 直接定址法
- 除留餘數法
- 數字分析法
- 平方取中法
上面展示的就是 除留餘數法 ，具體的細節這裏我就不再贅述，下面我們需要重點關注 第二個哈希函數 應該如何設計； 我們需要清楚 雙散列法 的雙散列，雖然指的是兩個 哈希函數 ，但是這兩個哈希函數均是作用於 同一個哈希表 ：
- 第一個 哈希函數 用於獲取 哈希地址
- 第二個 哈希函數 用於在遇到衝突時獲取 探測序列 （即前面所説的 地址增量）
因此我們在設計 第二個哈希函數 時，需要保證兩點：
- 其值不能為 $0$
- 其值需要與表長 互質
第一點我們很好理解，因為 第二個哈希函數 的作用是在遇到 哈希衝突 時，獲取 地址增量 ，若此時我們獲取的 地址增量 為 $0$ ，那就表示該 關鍵字 會停留在原地，一直髮生 哈希衝突； 第二點是為了確保探測序列能夠覆蓋散列表中的所有位置。這裏我們可以借用 除留餘數法 中 模數 選擇 質數 的原因來幫助理解：
- 在 除留餘數法 中，當 模數 為 合數 時，若 哈希函數 所映射的 哈希地址 與該 合數 存在 公因數 ，此時就會導致 關鍵字不均勻分佈 ；
- 當 模數 為 質數 時，除非 關鍵字序列 中的大部分 關鍵字 均為 模數 的倍數，否則，就能夠實現 關鍵字 的 均勻分佈
同理，當我們選擇 $Hash_2(key) = 1 + (key \bmod (m - 1))$ 作為 第二個哈希函數 時，實際上就是採取的 除留餘數法 的思想； 而當我們選擇 $Hash_2(key) = R - (key \bmod R)$ 時，則採取的是 偽隨機數 的思想，其中 $R$ 是一個小於 哈希表 大小的 質數； 因此，這裏介紹的兩種設計方案，均是為了使 關鍵字 在發生 哈希衝突 後，還能夠繼續保持 均勻分佈； 下面我們就以關鍵字序列 [19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79] 為例來説明 雙散列法 中的 插入 與 查找 操作的具體過程；
2.2 插入
對於這個擁有 $12$ 個 關鍵字 的 關鍵字序列 ，我們可以選擇使用下面這兩個 哈希函數：
- $Hash_1(key) = key \bmod 13$
- $Hash_2(key) = 13 - (key \bmod 13)$
確定了 哈希函數 ，接下來我們就來一步一步的將各個 關鍵字 插入到 哈希表 中：
- 插入 $19$
通過 $Hash_1(key) = 19 \bmod 13 = 6$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 6$ ，通過查表可知，此時該地址為 空閒地址 ，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 19 |
- 插入 $14$
通過 $Hash_1(key) = 14 \bmod 13 = 1$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 1$ ，通過查表可知，此時該地址為 空閒地址 ，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 14 | 19 |
- 插入 $23$
通過 $Hash_1(key) = 23 \bmod 13 = 10$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 10$ ，通過查表可知，此時該地址為 空閒地址 ，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 14 | 19 | 23 |
- 插入 $01$
通過 $Hash_1(key) = 01 \bmod 13 = 1$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 1$ ，通過查表可知，此時該地址已經存儲了 $key = 14$ ，導致其發生了 哈希衝突，因此我們需要通過 $Hash_2(key)$ 來獲取其 地址增量 從而獲得其新的地址：
$$ \begin{align*} Hash_2(key) &= 13 - (01 \bmod 13) = 12 \enspace {地址增量}\ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (1 + 1 * 12) \bmod 13 \ H_1 &= 0 \enspace {不衝突} \end{align*} $$
可以看到，通過 雙散列法 ，我們找到了 $key = 01$ 的新地址 $H_1 = 0$ ，並且該地址為 空閒地址，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 19 | 23 |
- 插入 $68$
通過 $Hash_1(key) = 68 \bmod 13 = 3$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 3$ ，通過查表可知，此時該地址為 空閒地址 ，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 19 | 23 |
- 插入 $20$
通過 $Hash_1(key) = 20 \bmod 13 = 7$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 7$ ，通過查表可知，此時該地址為 空閒地址 ，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 19 | 20 | 23 |
- 插入 $84$
通過 $Hash_1(key) = 84 \bmod 13 = 6$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 6$ ，通過查表可知，此時該地址已經存儲了 $key = 19$ ，導致其發生了 哈希衝突，因此我們需要通過 $Hash_2(key)$ 來獲取其 地址增量 從而獲得其新的地址：
$$ \begin{align*} Hash_2(key) &= 13 - (84 \bmod 13) = 7 \enspace {地址增量}\ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (6 + 1 * 7) \bmod 13 \ H_1 &= 0 \enspace {衝突} \ H_2 &= (Hash_1(key) + 2 * Hash_2(key)) \bmod 13 \ H_2 &= (6 + 2 * 7) \bmod 13 \ H_2 &= 7 \enspace {衝突} \ H_3 &= (Hash_1(key) + 3 * Hash_2(key)) \bmod 13 \ H_3 &= (6 + 3 * 7) \bmod 13 \ H_3 &= 1 \enspace {衝突} \ H_4 &= (Hash_1(key) + 4 * Hash_2(key)) \bmod 13 \ H_4 &= (6 + 4 * 7) \bmod 13 \ H_4 &= 8 \enspace {不衝突} \ \end{align*} $$
可以看到，通過 雙散列法 ，我們找到了 $key = 84$ 的新地址 $H_4 = 8$ ，並且該地址為 空閒地址，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 19 | 20 | 84 | 23 |
- 插入 $27$
通過 $Hash_1(key) = 27 \bmod 13 = 1$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 1$ ，通過查表可知，此時該地址已經存儲了 $key = 14$ ，導致其發生了 哈希衝突，因此我們需要通過 $Hash_2(key)$ 來獲取其 地址增量 從而獲得其新的地址：
$$ \begin{align*} Hash_2(key) &= 13 - (27 \bmod 13) = 12 \enspace {地址增量}\ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (1 + 1 * 12) \bmod 13 \ H_1 &= 0 \enspace {衝突} \ H_2 &= (Hash_1(key) + 2 * Hash_2(key)) \bmod 13 \ H_2 &= (1 + 2 * 12) \bmod 13 \ H_2 &= 12 \enspace {不衝突} \ \end{align*} $$
可以看到，通過 雙散列法 ，我們找到了 $key = 27$ 的新地址 $H_2 = 12$ ，並且該地址為 空閒地址，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 19 | 20 | 84 | 23 | 27 |
- 插入 $55$
通過 $Hash_1(key) = 55 \bmod 13 = 3$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 3$ ，通過查表可知，此時該地址已經存儲了 $key = 68$ ，導致其發生了 哈希衝突，因此我們需要通過 $Hash_2(key)$ 來獲取其 地址增量 從而獲得其新的地址：
$$ \begin{align*} Hash_2(key) &= 13 - (55 \bmod 13) = 10 \enspace {地址增量}\ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (3 + 1 * 10) \bmod 13 \ H_1 &= 0 \enspace {衝突} \ H_2 &= (Hash_1(key) + 2 * Hash_2(key)) \bmod 13 \ H_2 &= (3 + 2 * 10) \bmod 13 \ H_2 &= 10 \enspace {衝突} \ H_3 &= (Hash_1(key) + 3 * Hash_2(key)) \bmod 13 \ H_3 &= (3 + 3 * 10) \bmod 13 \ H_3 &= 7 \enspace {衝突} \ H_4 &= (Hash_1(key) + 4 * Hash_2(key)) \bmod 13 \ H_4 &= (3 + 4 * 10) \bmod 13 \ H_4 &= 4 \enspace {不衝突} \ \end{align*} $$
可以看到，通過 雙散列法 ，我們找到了 $key = 55$ 的新地址 $H_4 = 4$ ，並且該地址為 空閒地址，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 55 | 19 | 20 | 84 | 23 | 55 | 27 |
- 插入 $11$
通過 $Hash_1(key) = 11 \bmod 13 = 11$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 11$ ，通過查表可知，此時該地址為 空閒地址 ，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 55 | 19 | 20 | 84 | 23 | 11 | 27 |
- 插入 $10$
通過 $Hash_1(key) = 10 \bmod 13 = 10$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 10$ ，通過查表可知，此時該地址已經存儲了 $key = 23$ ，導致其發生了 哈希衝突，因此我們需要通過 $Hash_2(key)$ 來獲取其 地址增量 從而獲得其新的地址：
$$ \begin{align*} Hash_2(key) &= 13 - (10 \bmod 13) = 3 \enspace {地址增量}\ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (10 + 1 * 3) \bmod 13 \ H_1 &= 0 \enspace {衝突} \ H_2 &= (Hash_1(key) + 2 * Hash_2(key)) \bmod 13 \ H_2 &= (10 + 2 * 3) \bmod 13 \ H_2 &= 3 \enspace {衝突} \ H_3 &= (Hash_1(key) + 3 * Hash_2(key)) \bmod 13 \ H_3 &= (10 + 3 * 3) \bmod 13 \ H_3 &= 6 \enspace {衝突} \ H_4 &= (Hash_1(key) + 4 * Hash_2(key)) \bmod 13 \ H_4 &= (10 + 4 * 3) \bmod 13 \ H_4 &= 9 \enspace {不衝突} \ \end{align*} $$
可以看到，通過 雙散列法 ，我們找到了 $key = 10$ 的新地址 $H_4 = 9$ ，並且該地址為 空閒地址，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 55 | 19 | 20 | 84 | 10 | 23 | 11 | 27 |
- 插入 $79$
通過 $Hash_1(key) = 79 \bmod 13 = 1$ 可知，該 關鍵字 的 哈希地址 為 $Hash_1(key) = 1$ ，通過查表可知，此時該地址已經存儲了 $key = 14$ ，導致其發生了 哈希衝突，因此我們需要通過 $Hash_2(key)$ 來獲取其 地址增量 從而獲得其新的地址：
$$ \begin{align*} Hash_2(key) &= 13 - (79 \bmod 13) = 12 \enspace {地址增量}\ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (1 + 1 * 12) \bmod 13 \ H_1 &= 0 \enspace {衝突} \ H_2 &= (Hash_1(key) + 2 * Hash_2(key)) \bmod 13 \ H_2 &= (1 + 2 * 12) \bmod 13 \ H_2 &= 12 \enspace {衝突} \ H_3 &= (Hash_1(key) + 3 * Hash_2(key)) \bmod 13 \ H_3 &= (1 + 3 * 12) \bmod 13 \ H_3 &= 11 \enspace {衝突} \ H_4 &= (Hash_1(key) + 4 * Hash_2(key)) \bmod 13 \ H_4 &= (1 + 4 * 12) \bmod 13 \ H_4 &= 10 \enspace {衝突} \ H_5 &= (Hash_1(key) + 5 * Hash_2(key)) \bmod 13 \ H_5 &= (1 + 5 * 12) \bmod 13 \ H_5 &= 9 \enspace {衝突} \ H_6 &= (Hash_1(key) + 6 * Hash_2(key)) \bmod 13 \ H_6 &= (1 + 6 * 12) \bmod 13 \ H_6 &= 8 \enspace {衝突} \ H_7 &= (Hash_1(key) + 7 * Hash_2(key)) \bmod 13 \ H_7 &= (1 + 7 * 12) \bmod 13 \ H_7 &= 7 \enspace {衝突} \ H_8 &= (Hash_1(key) + 8 * Hash_2(key)) \bmod 13 \ H_8 &= (1 + 8 * 12) \bmod 13 \ H_8 &= 6 \enspace {衝突} \ H_9 &= (Hash_1(key) + 9 * Hash_2(key)) \bmod 13 \ H_9 &= (1 + 9 * 12) \bmod 13 \ H_9 &= 5 \enspace {不衝突} \ \end{align*} $$
可以看到，通過 雙散列法 ，我們找到了 $key = 79$ 的新地址 $H_9 = 5$ ，並且該地址為 空閒地址，因此直接插入該 關鍵字：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 55 | 79 | 19 | 20 | 84 | 10 | 23 | 11 | 27 |
通過這裏的實例我們可以看到，$Hash_2(key)$ 所計算的並不是 關鍵字 的最終地址，而是其發生衝突後的 地址增量； 從上述的例子可以得出一個結論：
- 使用 雙散列法 處理衝突的 哈希表 ，當 關鍵字 發生衝突時，其處理衝突的方式與 線性探測法 一致，均採用的是 固定步長探測 ，它們之間的差異在於 探測步長 的不同：
- 線性探測法 中，每一個 關鍵字 的 固定探測步長 均為 $1$
- 雙散列法 中，不同 關鍵字 的 固定探測步長 由 $Hash_2(key)$ 計算獲得
2.3 查找
瞭解了 雙散列法 的 插入操作 ，接下來我們就來簡單説明一下其 查找操作； 與之前介紹的 線性探測法、平方探測法、偽隨機序列法 一致，其查找的過程中，按查找是否成功可以分為兩大類：
- 查找成功：通過 雙散列函數 成功在表中找到了 目標關鍵字
- 查找失敗：通過 雙散列函數 在表中未能找到 目標關鍵字，並且根據 哈希表 的裝載狀態可以分為兩類：
- 哈希表 為 滿載狀態，即 $\alpha = 1$，此時從 起始點 出發，最終回到了 起始點，這就表示表中不存在 目標關鍵字
- 哈希表 還存在 空閒地址，即 $\alpha < 1$ ，此時若探測到了 空閒地址，也表示表中不存在 目標關鍵字
這裏我們舉一個例子，比如我們要在表中查找 $key = 12$ ，其具體的查找步驟如下：
- 通過 $Hash_1(key)$ 確定其 哈希地址
$$ Hash_1(key) = 12 \bmod 13 = 12 $$
- 通過 哈希地址 進行首次查找
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 01 | 14 | 68 | 55 | 79 | 19 | 20 | 84 | 10 | 23 | 11 | 27 |
從 哈希表 中我們可以獲取 $Hash(12) = 27 \neq 12$ ，因此我們需要通過 $Hash_2(key)$ 進行探測，繼續查找；
- 通過 $Hash_2(key)$ 進行 探測查找
$$ \begin{align*} Hash_2(key) &= 13 - (12 \bmod 13) = 1 \enspace {探測步長} \ H_1 &= (Hash_1(key) + 1 * Hash_2(key)) \bmod 13 \ H_1 &= (12 + 1 * 1) \bmod 13 \ H_1 &= 0 \ Hash(0) &= 01 \neq 12 \ H_2 &= (Hash_1(key) + 2 * Hash_2(key)) \bmod 13 \ H_2 &= (12 + 2 * 1) \bmod 13 \ H_2 &= 1 \ Hash(1) &= 14 \neq 12 \ H_3 &= (Hash_1(key) + 3 * Hash_2(key)) \bmod 13 \ H_3 &= (12 + 3 * 1) \bmod 13 \ H_3 &= 2 \ Hash(2) &= {空閒地址} \ \end{align*} $$
通過 探測查找 我們發現此時我們找到的 $Hash(2)$ 是一個 空閒地址 ，這就表明該 哈希表 中並不存在 $key = 12$ 這個 關鍵字 ，因此本次 查找失敗；
2.4 優勢與侷限
2.4.1 優勢
雙散列法 的優勢主要體現在其 探測序列 的獨特性上：
- 出色的數據分佈能力
由於 第二個散列函數 $\bm{Hash_2(key)}$ 為不同的關鍵字生成不同的、固定的探測步長 。 這使得即使多個關鍵字的初始哈希地址相同，它們的探測路徑也會迅速分岔擴散，從而最大限度地減少了聚集（Clustering）現象 。 數據在表中分佈得更均勻，這在哈希表負載因子（已存儲元素數與總槽位數的比值）升高時尤為重要，能保持相對穩定的操作性能。
- 較高的空間利用率
與 拉鍊法 需要為每個槽位維護額外的指針空間相比，雙散列法 作為 開放尋址法 的一種，所有數據都存儲在基礎的數組結構中，空間開銷更小 。在數據記錄本身較大時，這種空間優勢更明顯。
2.4.2 侷限性
雙散列法也並非完美，其侷限性主要在於 實現 和 負載方面 的要求：
- 實現相對複雜
雙散列法需要設計並計算 兩個散列函數，這比 線性探測 或 二次探測的實現要複雜一些，計算開銷也稍大 。 更重要的是，第二個 散列函數 $Hash_2(key)$ 的設計有嚴格要求：
- 其計算結果絕不能為0（否則會陷入死循環）
- $Hash_2(key)$ 的值應與 哈希表 大小 $m$ 互質（即最大公約數為$1$），以確保探測序列能夠遍歷整個哈希表 。
一個常見的技巧是讓表大小 $m$ 取質數，並設計 $Hash_2(key)$ 使其結果落在 $[1, m-1]$範圍內。
- 高負載時性能下降
當 哈希表 的 負載因子 接近 $1$（即錶快被填滿）時，雙散列法 的性能會顯著下降，插入 和 查找 操作可能需要很長的 探測序列，甚至可能因為不斷探測已佔用的槽位而陷入循環，導致插入失敗 。 因此，使用 雙散列法（以及其他 開放尋址法）時，通常需要通過再散列（Rehashing） 來動態擴容，即 當負載因子超過某個閾值（如$0.7$ 或 $0.75$）時，創建一個更大的新表，並將所有元素重新哈希到新表中。
結語
在今天的內容中我們介紹了兩種 開放定址法：
- 偽隨機序列法：在發生衝突時，通過 偽隨機數生成器 生成一個 偽隨機序列 作為 探測序列
- 雙散列法：在發生衝突時，通過 第二個哈希函數 計算出一個 獨屬於該關鍵字的固定探測步長 進行 固定步長探測
相比於 線性探測法 以及 平方探測法 ，這兩種方法均能夠有效的避免 聚集問題； 但是這兩種方法都需要通過計算獲取 關鍵字 的 探測序列 ，這就使得其實現會比 線性探測法 以及 平方探測法 更加的困難； 不知道大家有沒有發現，在我們介紹的這 $4$ 種 開放定址法 中，都存在一個相同的問題：
- 高負載時，哈希表的性能下降
那麼在 開放定址法 中 裝填因子 對 哈希表 的性能又會有何影響呢？ 在下一篇內容中，我們將會詳細探討 哈希表的性能 ，大家記得關注哦！ 互動與分享
-
點贊👍 - 您的認可是我持續創作的最大動力
-
收藏⭐ - 方便隨時回顧這些重要的基礎概念
-
轉發↗️ - 分享給更多可能需要的朋友
-
評論💬 - 歡迎留下您的寶貴意見或想討論的話題
感謝您的耐心閲讀！ 關注博主，不錯過更多技術乾貨。我們下一篇再見！
