【数据结构】考研408 | 伪随机探测与双重散列精讲：散列的艺术与均衡之道

(开放定址法)

导读

大家好，很高兴又和大家见面啦！！！ 通过前面的内容，我们已经学习了两种 开放定址法 ：

• 线性探测法：通过 固定探测步长 处理冲突
• 平方探测法：通过 平方跳跃步长 处理冲突

但是这两种方法均会带来一定的问题：

• 线性探测法 会导致 一次聚集 的现象
• 平方探测法 会导致 二次聚集 的现象

因此，在 开放定址法 中是否存在着能够避免这种 聚集现象 的冲突处理方法呢？ 答案是肯定的，这就是我们今天要介绍的 伪随机数法 以及 双散列法。 接下来就让我们一起深入探讨一下这两种方法是如何做到在处理冲突的同时还能够避免 聚集现象；

一、伪随机序列法

伪随机序列法 指的是人为的设置一个 伪随机序列 d_i ，如

当发生冲突时，按照 伪随机序列 去进行 循环探测 ，直到找到 空闲地址； 熟悉 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。 双散列法 的 哈希函数 形式为：

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 ，通过查表可知，此时该地址为 空闲地址 ，因此直接插入该 关键字：

• 插入 14

通过 Hash_1(key) = 14 \bmod 13 = 1 可知，该 关键字 的 哈希地址 为 Hash_1(key) = 1 ，通过查表可知，此时该地址为 空闲地址 ，因此直接插入该 关键字：

• 插入 23

通过 Hash_1(key) = 23 \bmod 13 = 10 可知，该 关键字 的 哈希地址 为 Hash_1(key) = 10 ，通过查表可知，此时该地址为 空闲地址 ，因此直接插入该 关键字：

• 插入 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 ，并且该地址为 空闲地址，因此直接插入该 关键字：

• 插入 68

通过 Hash_1(key) = 68 \bmod 13 = 3 可知，该 关键字 的 哈希地址 为 Hash_1(key) = 3 ，通过查表可知，此时该地址为 空闲地址 ，因此直接插入该 关键字：

• 插入 20

通过 Hash_1(key) = 20 \bmod 13 = 7 可知，该 关键字 的 哈希地址 为 Hash_1(key) = 7 ，通过查表可知，此时该地址为 空闲地址 ，因此直接插入该 关键字：

• 插入 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 ，并且该地址为 空闲地址，因此直接插入该 关键字：

• 插入 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 ，并且该地址为 空闲地址，因此直接插入该 关键字：

• 插入 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 ，并且该地址为 空闲地址，因此直接插入该 关键字：

• 插入 11

通过 Hash_1(key) = 11 \bmod 13 = 11 可知，该 关键字 的 哈希地址 为 Hash_1(key) = 11 ，通过查表可知，此时该地址为 空闲地址 ，因此直接插入该 关键字：

• 插入 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 ，并且该地址为 空闲地址，因此直接插入该 关键字：

• 插入 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 ，并且该地址为 空闲地址，因此直接插入该 关键字：

通过这里的实例我们可以看到，Hash_2(key) 所计算的并不是 关键字 的最终地址，而是其发生冲突后的 地址增量； 从上述的例子可以得出一个结论：

• 使用 双散列法 处理冲突的 哈希表 ，当 关键字 发生冲突时，其处理冲突的方式与 线性探测法 一致，均采用的是 固定步长探测 ，它们之间的差异在于 探测步长 的不同： 线性探测法 中，每一个 关键字 的 固定探测步长 均为 1 双散列法 中，不同 关键字 的 固定探测步长 由 Hash_2(key) 计算获得

2.3 查找

了解了 双散列法 的 插入操作 ，接下来我们就来简单说明一下其 查找操作； 与之前介绍的 线性探测法、平方探测法、伪随机序列法 一致，其查找的过程中，按查找是否成功可以分为两大类：

• 查找成功：通过 双散列函数 成功在表中找到了 目标关键字
• 查找失败：通过 双散列函数 在表中未能找到 目标关键字，并且根据 哈希表 的装载状态可以分为两类： 哈希表 为 满载状态，即 \alpha = 1，此时从 起始点 出发，最终回到了 起始点，这就表示表中不存在 目标关键字 哈希表 还存在 空闲地址，即 \alpha < 1

这里我们举一个例子，比如我们要在表中查找 key = 12 ，其具体的查找步骤如下：

• 通过 Hash_1(key) 确定其 哈希地址

• 通过 哈希地址 进行首次查找

从 哈希表 中我们可以获取 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) 的设计有严格要求：

1. 其计算结果绝不能为0（否则会陷入死循环）
2. Hash_2(key) 的值应与 哈希表 大小 m 互质（即最大公约数为1），以确保探测序列能够遍历整个哈希表 。

一个常见的技巧是让表大小 m 取质数，并设计 Hash_2(key) 使其结果落在 [1, m-1]范围内。

• 高负载时性能下降

当 哈希表 的 负载因子 接近 1（即表快被填满）时，双散列法 的性能会显著下降，插入 和 查找 操作可能需要很长的 探测序列，甚至可能因为不断探测已占用的槽位而陷入循环，导致插入失败 。 因此，使用 双散列法（以及其他 开放寻址法）时，通常需要通过再散列（Rehashing）​ 来动态扩容，即 当负载因子超过某个阈值（如0.7 或 0.75）时，创建一个更大的新表，并将所有元素重新哈希到新表中。

结语

在今天的内容中我们介绍了两种 开放定址法：

• 伪随机序列法：在发生冲突时，通过 伪随机数生成器 生成一个 伪随机序列 作为 探测序列
• 双散列法：在发生冲突时，通过 第二个哈希函数 计算出一个 独属于该关键字的固定探测步长 进行 固定步长探测

相比于 线性探测法 以及 平方探测法 ，这两种方法均能够有效的避免 聚集问题； 但是这两种方法都需要通过计算获取 关键字 的 探测序列 ，这就使得其实现会比 线性探测法 以及 平方探测法 更加的困难； 不知道大家有没有发现，在我们介绍的这 4 种 开放定址法 中，都存在一个相同的问题：

• 高负载时，哈希表的性能下降

那么在 开放定址法 中 装填因子 对 哈希表 的性能又会有何影响呢？ 在下一篇内容中，我们将会详细探讨 哈希表的性能 ，大家记得关注哦！ 互动与分享

• 点赞👍 - 您的认可是我持续创作的最大动力
• 收藏⭐ - 方便随时回顾这些重要的基础概念
• 转发↗️ - 分享给更多可能需要的朋友
• 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！