【数据结构】考研408 | 平方探测法精讲：跳跃探查的艺术与聚集迷思

(开放定址法)

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇内容中我们介绍了 开放定址法 的第一种方法——线性探测法。其处理冲突的方式为：

• 当发生冲突时，顺序查找表中的下一个单元，直到找到表中的一个空闲单元，或查遍全表。

这种 固定步长探测序列 使得其 实现简单，但同时会导致大量的同义词与非同义词的 聚集现象； 聚集现象 对于一个 哈希表 而言，是致命的，因为它会严重降低 哈希表 的性能，甚至是使得 哈希表 退化为 数组； 那么我们应该在保证能够解决冲突的前提下，还能够避免 聚集现象 呢？ 这就是我们今天要介绍的 平方探测法，接下来就让我们一起对其进行深入探讨；

一、基本思想

平方探测法 也称 二次探测法。其基本思想为：通过使用探测次数的平方，来改变探测的步长，使发生冲突的关键字以更“跳跃”的方式寻找新位置。 在 线性探测法 中，其 探测序列 为：

从该 探测序列 我们不难发现，它是一个 固定步长 的 探测序列，因此我们不难想象，在处理冲突的过程中，同义词与非同义词会在表中形成一块很大的 连续占用空间； 而 平方探测法 的探测序列为：

其中 k \leq \frac{m}{2}； 这里我们可以理解为，在 平方探测法 中，整个探测的过程都是以 起始点 也就是 哈希地址 为中心，依次向其左右两侧进行探测：

• 当探测序列为正数时，往 哈希地址 的右侧探测
• 当探测序列为负数时，往 哈希地址 的左侧探测

就如上表所示，正数就往右探测，负数就往左探测。但是不同的是它并不是无限的向两边扩散，根据其探测推导式：

整个探测过程实际上也是一种 循环探测，但是由于其探测值 d_i 可能在为负值的情况下导致 Hash(key) + d_i < 0

其中：k \in N^+ 就比如上表中Hash(key) = 6, m = 13 ，当 d_i = - 3^2 时，其具体的探测地址为：

$$ \begin{align*} H_i &= (6 - 4^2) \bmod 13 \ H_i &= -10 \ H_i &= (-10 + 13) \bmod 13 \ H_i &= 3 \ \end{align*} $$

根据此时的处理，我们就得到了其具体的探测地址为 H_i = 3 的地址处；

二、探测过程

了解了 平方探测法 的基本思想，接下来我们就通过实例来介绍 平方探测法 的具体过程； 现在我们需要将关键字序列 [8, 10, 16, 20, 40, 50, 55, 60, 69, 77, 80, 85] 插入到表长为 12 的 哈希表 中，这里我们选择的 哈希函数 为：

接下来我们就可以通过该 哈希函数 进行 插入 操作了；

• 插入 8

关键字 key = 8 对应的 哈希地址 为：Hash(key) = 8 \bmod 11 = 8 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 10

关键字 key = 10 对应的 哈希地址 为：Hash(key) = 10 \bmod 11 = 10 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 16

关键字 key = 16 对应的 哈希地址 为：Hash(key) = 16 \bmod 11 = 5 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 20

关键字 key = 20 对应的 哈希地址 为：Hash(key) = 20 \bmod 11 = 9 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 40

关键字 key = 40 对应的 哈希地址 为：Hash(key) = 40 \bmod 11 = 7 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 50

关键字 key = 50 对应的 哈希地址 为：Hash(key) = 50 \bmod 11 = 6 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 55

关键字 key = 55 对应的 哈希地址 为：Hash(key) = 55 \bmod 11 = 0 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 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^2) \bmod 12 = 6 \enspace {冲突} \ H_2 &= (5 + -1^2) \bmod 12 = 4 \enspace {不冲突} \end{align*} $$

通过 平方探测法 我们发现，当出现 2 次 冲突 后，我们在下标为 4 的 空闲地址，因此我们需要将 key = 60 插入到该地址处：

• 插入 69

关键字 key = 69 对应的 哈希地址 为：Hash(key) = 69 \bmod 11 = 3 ，通过查表可以看到，当前地址中没有任何 关键字 ，因此可以直接插入：

• 插入 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^2) \bmod 12 = 1 \enspace {不冲突} \ \end{align*} $$

通过 平方探测法 我们发现，当出现 1 次 冲突 后，我们在下标为 1 的 空闲地址，因此我们需要将 key = 77 插入到该地址处：

• 插入 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^2) \bmod 12 = 4 \enspace {冲突} \ H_2 &= (3 - 1^2) \bmod 12 = 2 \enspace {不冲突} \ \end{align*} $$

通过 平方探测法 我们发现，当出现 2 次 冲突 后，我们在下标为 2 的 空闲地址，因此我们需要将 key = 80 插入到该地址处：

• 插入 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^2) \bmod 12 = 9 \enspace {冲突} \ H_2 &= (8 - 1^2) \bmod 12 = 10 \enspace {冲突} \ H_3 &= (8 + 2^2) \bmod 12 = 0 \enspace {冲突} \ H_4 &= (8 - 2^2) \bmod 12 = 4 \enspace {冲突} \ H_5 &= (8 + 3^2) \bmod 12 = 5 \enspace {冲突} \ H_6 &= (8 - 3^2) \bmod 12 = -1 \enspace {结果为负数，进一步处理} \ H_6 &= (-1 + 12) \bmod 12 = 11 \enspace {不冲突} \ \end{align*} $$

通过 平方探测法 我们发现，当出现 6 次 冲突 后，我们在下标为 11 的 空闲地址，因此我们需要将 key = 85 插入到该地址处：

此时我们就完成了全部的插入过程。

三、优势与局限

3.1 优势

平方探测法 的 跳跃性 探测给它带来了一些优势：

• 有效避免一次聚集

在 线性探测法 中，正是因为 固定的探测步长 ，这就导致了在处理冲突时，同义词与非同义词会在发生冲突后形成一大块 连续的区域 ，从而降低了 哈希表 的性能； 而 平方探测法 通过 平方增量跳跃式探测，分散冲突元素，缓解了线性探测的 聚集问题。

• 缓存性能尚可

在 平方探测法 中数据仍大致存储在连续区域内，相比 拉链法 通过额外的链表来存储数据，平方探测法 有更好的缓存局部性。

• 实现相对简单

线性探测法 只需要在发生冲突后，顺序向后循环查找，其算法逻辑非常简单； 平方探测法 相比于 线性探测法 ，在发生冲突后，并不是向后顺序查找，而是通过 平方增量 进行 跳跃式查找 ，因此算法逻辑也不复杂，实现起来也比较简单；

3.2 局限

但是，与 线性探测法 一样，平方探测法 虽然通过 平方跳跃式 的查找来解决冲突，避免了 一次聚集 的问题，但也正是这种 平方跳跃，它也带来了新的问题

3.2.1 二次聚集

虽然 平方探测法 采用了 平方跳跃 来避免了 顺序查找 带来的 一次聚集，但是仍然存在当 地址重合 时引发的 二次聚集； 举一个很简单的例子，在使用了 Hash(key) = key \bmod 11 这个 哈希函数 的情况下进行的 哈希存储 ，当我们在存储 18、30 这两个元素时，它们的初始地址分别为：

$$ \begin{align*} Hash(18) &= 18 \bmod 11 = 7 \ Hash(30) &= 30 \bmod 11 = 8 \end{align*} $$

显然，这两个是 非同义词 ，那么当他们通过 平方探测法 查找空闲地址时：

$$ \begin{align*} H_i &= (7 + 1^2) \bmod 11 = 8 \ H_i &= (8 + 0^2) \bmod 11 = 8 \ H_i &= (7 + 0^2) \bmod 11 = 7 \ H_i &= (8 - 1^2) \bmod 11 = 7 \end{align*} $$

可以看到，他们会出现查找到同一地址的概率，因此会导致出现不同于 一次聚集 的 二次聚集； 二次聚集 是由 相同的探测序列 引发的 聚集现象，这种现象对于同义词与非同义词就会存在两种情况：

• 同义词：初始地址相同，探测序列相同，导致出现很长的冲突路径
• 非同义词：初始地址不同，探测序列相同，导致出现相交的冲突结点

3.2.2 探测路径可能不全

由于 平方探测法 采用的是 跳跃探测 ，因此会出现可能无法探测到哈希表 上的所有单元这种情况，但至少能探测到一半单元。 就比如当 哈希表 的表长为 m = 5 时，那么对于 初始地址 在 Hash(key) = 0、Hash(key) = 1、Hash(key) = 2 这些位置上的 关键字 而言，当发生冲突时：

$$ \begin{align*} H_1 = (1 + 1 ^ 2) \bmod 5 = 2 \ H_2 = (1 - 1 ^ 2) \bmod 5 = 0 \ H_3 = (1 + 2 ^ 2) \bmod 5 = 0 \ H_4 = (1 - 2 ^ 2) \bmod 5 = -3 \ H_4 = (-3 + 5) \bmod 5 = 2 \ H_5 = (1 + 3^2) \bmod 5 = 0 \ H_6 = (1 - 3^2) \bmod 5 = -3 \ H_6 = (-3 + 5) \bmod 5 = 2 \end{align*} $$

可以看到，此时通过 平方探测法 只能探测到 0, 2 这两个地址，而无法探测到 3, 4 这两个地址；

为了保证平方探测法的有效性和性能，对哈希表的参数有两个关键要求：

1. 表长要求

哈希表 的表长最好是一个 质数。这能最有效地减少 哈希函数的初始冲突，是 散列表 设计的通用优化原则。 一个更强且能保证探测序列遍历整个表的充分条件是：表长为形如 m = 4k + 3 的 质数。数学上可以证明，此条件能彻底避免 探测路径不全 的问题，因为它保证了 平方探测序列 可以探测到 哈希表 中的每一个位置。

1. 装载因子限制

在满足上述表长要求（特别是表长为质数）的基础上，平方探测法的性能对 装载因子 非常敏感。一个重要的定理指出：

• 当 表长是质数，且 哈希表 至少有一半是空的（即装载因子 \alpha \leq 0.5）时，平方探测法 可以保证插入成功，并且在整个探测过程中不会访问到重复的位置。

这也意味着 哈希表 的空间利用率通常需保持在 50% 以下，我们将在后续的性能评估篇章中对其影响进行详细探讨。

3.2.3 删除操作需特殊处理

平方探测法 和 线性探测法 一样，才用 平方探测法 的 哈希表 在执行 删除操作 时，需采用“逻辑删除”； 具体原因在 线性探测法 中有过详细介绍，这里我就不再展开；

四、概念辨析

我们需要注意一个概念 二次聚集，下面我们就来深入探讨一下 二次聚集；

4.1 两种理解

在 哈希表 中，不同的教材和实践中存在着不同的理解角度：

4.1.1 角度一：由非同义词引发

在这种角度下，二次聚集 特指的是 由非同义词争夺同一后继地址引发的新冲突； 严蔚敏教授的教材中采取的就是该角度的理解； 在这种角度的支持下，二次聚集 就并不是发生在 平方探测法 中，而是在 线性探测法 中也同样存在： 当 Hash(key) = a 这个位置发生冲突时，这个位置的同义词发生的冲突称为 一次聚集 ，若此时 非同义词 通过 线性探测法 导致在该位置发生冲突时，这种情况就被称为 二次聚集 或者叫做 堆积；

4.1.2 角度二：由同义词引发

在这种角度下，二次聚集 泛指所有映射到同一地址的 同义词 在共享 相同探测序列 的情况下导致的 性能下降； 由于 平方探测法 的探测序列为：

对于 同义词 而言，他们的 起始地址相同，探测序列相同，这就导致了他们的 探测路径完成一致，因此就导致了在该 探测路径 下出现了 同义词 的 扎堆现象，从而导致了 哈希表 的 性能下降； 在该视角下，因 探测序列 相同导致的任何 性能恶化 都可以被宽泛地称为 二次聚集； 因此，该视角下的 非同义词 既是 初始地址不同 ，但是由于 探测序列相同，同样会出现双方的 探测路径交叉 的现象，在双方的 交叉点 处就会发生 非同义词冲突 ，这也被称为 二次聚集； 不难发现，上文我所介绍的 二次聚集 正是基于该视角； 但是严格来说，因为我所学的是基于严蔚敏教授的《数据结构》所编写的教材，因此我应该采用第一种视角才对； 不过与我个人而言，要真正理解 二次冲突 显然第二种视角会更合适一点，因此我才会采用第二种视角； 这两种视角的区别大家有过相关的了解即可，具体选择哪一种视角，这就需要看各位的具体选择了；

结语

在今天的内容中我们介绍了 平方探测法 的详细内容，下面我们简单的对上文内容做一个回顾：

• 基本思想

平方探测法 是指 通过探测次数的平方，来改变探测的步长，是发生冲突的关键字以更跳跃的方式寻找新位置 平方探测法 的 探测序列 是固定的：d_i = 0^2, 1^2, -1^2, 2^2, -2^2, \cdots, k^2, -k^2 \ k \leq \frac{m}{2}

• 优势

平方探测法 有校避免了 一次聚集，并且其 缓存性能尚可，由于其 算法逻辑简单，所以其 实现也相对简单；

• 局限性

平方探测法 在避免了 一次聚集 的同时也带来了 二次聚集； 由于其 平方跳跃探测 ，这就导致了其存在 探测路径不全 的问题，为此使用 平方探测法 的 哈希表 表长首选 质数，其中采用形如 m = 4k+3的 质数 是保证 探测序列完备 的强条件； 与 线性探测法 一样，平方探测法 在进行 删除 操作时，同样只能使用 逻辑删除 那么除了 线性探测法 与 平方探测法 是否还存在其它的 开放定址法 用于解决冲突呢？ 答案是肯定的，在下一篇的内容中，我们将会介绍两种新的 开放定址法，大家记得关注哦！ 互动与分享

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

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