深入理解开放寻址法中的三种探测序列

一、引言

开放寻址法是解决散列表中冲突的一种重要方法，当发生冲突（即两个不同的键通过散列函数计算得到相同的散列值）时，它会在散列表中寻找下一个可用的存储位置。而探测序列就是用于确定在发生冲突后，依次尝试哪些存储位置的规则。下面详细介绍线性探测、二次探测和双重散列这三种常见的探测序列。

二、线性探测（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,\cdots$），$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,\cdots$），$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,\cdots$），$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.优缺点

• 优点：是开放寻址法中最好的方法之一，能更均匀地分布键，减少聚集现象，使插入、查找和删除操作的平均性能更接近理想情况。
• 缺点：需要设计两个散列函数，实现相对复杂，计算开销也会稍微大一些。