一、引言

開放尋址法是解決散列表中沖突的一種重要方法，當發生沖突（即兩個不同的鍵通過散列函數計算得到相同的散列值）時，它會在散列表中尋找下一個可用的存儲位置。而探測序列就是用于確定在發生沖突后，依次嘗試哪些存儲位置的規則。下面詳細介紹線性探測、二次探測和雙重散列這三種常見的探測序列。

二、線性探測（Linear Probing）

1. 原理

線性探測是最簡單的開放尋址法探測序列。當插入一個鍵值對，計算出的散列值對應的存儲位置已被占用時，它會按照順序依次檢查下一個存儲位置（通常是逐個向后檢查），直到找到一個空的存儲位置為止。如果檢查到散列表的末尾還沒有找到空位置，就會從散列表的開頭繼續檢查。其探測函數的公式為：
$$h(k,i)=(h^{\prime }(k)+i)\mathrm{mod}m$$
其中，$h(k,i)$ 是經過 $i$ 次探測后得到的存儲位置，$h^{\prime }(k)$ 是初始的散列值（即通過散列函數直接計算得到的位置），$i$ 是探測次數（$i=0,1,2,?$），$m$ 是散列表的大小。

2. 示例

假設散列表的大小 $m=10$，散列函數 $h^{\prime }(k)=k\mathrm{mod}10$。現在要依次插入鍵 $23$、$33$、$43$。

• 插入鍵 $23$：$h^{\prime }(23)=23\mathrm{mod}10=3$，位置 $3$ 為空，直接插入。
• 插入鍵 $33$：$h^{\prime }(33)=33\mathrm{mod}10=3$，位置 $3$ 已被占用，進行第一次探測 $i=1$，$h(33,1)=(3+1)\mathrm{mod}10=4$，位置 $4$ 為空，插入到位置 $4$。
• 插入鍵 $43$：$h^{\prime }(43)=43\mathrm{mod}10=3$，位置 $3$ 已被占用，進行第一次探測 $i=1$，$h(43,1)=(3+1)\mathrm{mod}10=4$，位置 $4$ 也被占用，進行第二次探測 $i=2$，$h(43,2)=(3+2)\mathrm{mod}10=5$，位置 $5$ 為空，插入到位置 $5$。

3. 優缺點

• 優點：實現簡單，只需要進行簡單的加法和取模運算。
• 缺點：容易產生“聚集”現象，即連續被占用的存儲位置會越來越長，導致后續插入和查找操作的效率降低。

三、二次探測（Quadratic Probing）

1. 原理

二次探測通過二次函數來確定探測序列，它在發生沖突時，不是像線性探測那樣逐個向后檢查，而是按照二次方的步長來檢查存儲位置。其探測函數的公式為：
$$h(k,i)=(h^{\prime }(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$$
其中，$c_1$ 和 $c_2$ 是正的常數，$h^{\prime }(k)$ 是初始散列值，$i$ 是探測次數（$i=0,1,2,?$），$m$ 是散列表的大小。常見的情況是 $c_1=c_2=1$。

2. 示例

同樣假設散列表的大小 $m=10$，散列函數 $h^{\prime }(k)=k\mathrm{mod}10$，$c_1=c_2=1$。要插入鍵 $23$、$33$、$43$。

• 插入鍵 $23$：$h^{\prime }(23)=23\mathrm{mod}10=3$，位置 $3$ 為空，直接插入。
• 插入鍵 $33$：$h^{\prime }(33)=33\mathrm{mod}10=3$，位置 $3$ 已被占用，進行第一次探測 $i=1$，$h(33,1)=(3+1\times 1+1\times 1^2)\mathrm{mod}10=5$，位置 $5$ 為空，插入到位置 $5$。
• 插入鍵 $43$：$h^{\prime }(43)=43\mathrm{mod}10=3$，位置 $3$ 已被占用，進行第一次探測 $i=1$，$h(43,1)=(3+1\times 1+1\times 1^2)\mathrm{mod}10=5$，位置 $5$ 也被占用，進行第二次探測 $i=2$，$h(43,2)=(3+1\times 2+1\times 2^2)\mathrm{mod}10=9$，位置 $9$ 為空，插入到位置 $9$。

3. 優缺點

• 優點：一定程度上緩解了線性探測的“聚集”問題，因為它的探測步長是變化的。
• 缺點：仍然可能出現二次聚集的情況，即不同的初始散列值可能會產生相同的探測序列。

四、雙重散列（Double Hashing）

1. 原理

雙重散列使用兩個散列函數來確定探測序列。當發生沖突時，它會根據第二個散列函數計算出的步長來依次檢查存儲位置。其探測函數的公式為：
$$h(k,i)=(h_1(k)+i\times h_2(k))\mathrm{mod}m$$
其中，$h_1(k)$ 是第一個散列函數計算得到的初始散列值，$h_2(k)$ 是第二個散列函數，$i$ 是探測次數（$i=0,1,2,?$），$m$ 是散列表的大小。為了保證能夠遍歷散列表中的所有位置，$h_2(k)$ 的值必須與 $m$ 互質。

2. 示例

假設散列表的大小 $m=10$，第一個散列函數 $h_1(k)=k\mathrm{mod}10$，第二個散列函數 $h_2(k)=7?(k\mathrm{mod}7)$。要插入鍵 $23$、$33$、$43$。

• 插入鍵 $23$：$h_1(23)=23\mathrm{mod}10=3$，位置 $3$ 為空，直接插入。
• 插入鍵 $33$：$h_1(33)=33\mathrm{mod}10=3$，位置 $3$ 已被占用，$h_2(33)=7?(33\mathrm{mod}7)=7?5=2$，進行第一次探測 $i=1$，$h(33,1)=(3+1\times 2)\mathrm{mod}10=5$，位置 $5$ 為空，插入到位置 $5$。
• 插入鍵 $43$：$h_1(43)=43\mathrm{mod}10=3$，位置 $3$ 已被占用，$h_2(43)=7?(43\mathrm{mod}7)=7?1=6$，進行第一次探測 $i=1$，$h(43,1)=(3+1\times 6)\mathrm{mod}10=9$，位置 $9$ 為空，插入到位置 $9$。

3.優缺點

• 優點：是開放尋址法中最好的方法之一，能更均勻地分布鍵，減少聚集現象，使插入、查找和刪除操作的平均性能更接近理想情況。
• 缺點：需要設計兩個散列函數，實現相對復雜，計算開銷也會稍微大一些。