【数据结构】考研408 | 开放定址法精讲：连续探测的艺术与代价

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇内容中我们介绍了 处理冲突 的一种经典策略——拉链法：

• 通过 数组 + 链表 的组合，不仅有效的处理了冲突，还避免了堆积现象

虽然 拉链法 的优势突出，但是 链表 同时也带来了一些局限性：

• 每一个结点都需要一个 额外的指针空间

今天我们将会介绍另一种 冲突处理策略 —— 开放定址法。我们会了解到，如何在不消耗 额外空间 的情况下，实现对 哈希冲突 的处理。下面就让我们一起进入今天的主题；

一、基本概念

1.1 开放定址法

开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：

式中：

• H(key) 是 哈希函数
• i 可理解为“第 i 次发生冲突”，且 i=0,1,2,……,k(k \leq m-1)
• m 表示散列表表长；
• d_i为增量序列；

简单的说，当我们通过 哈希函数 获取的 哈希地址 中存在 关键字 时，就会发生 冲突 ，此时我们就可以考虑将 关键字 存放到其它 空闲地址； 如，我们通过 哈希函数 Hash(key) = key \bmod 10 来存放数据 [1, 11, 2]：

• 首先我们通过 哈希函数 确认了 key = 1 的 哈希地址 Hash(key) = 1 \bmod 10 = 1并将其进行存放：

此时由于表为一个 空表 ，因此 关键字 能够直接存放：

• 之后我们再一次通过 哈希函数 确认了 key = 11 的 哈希地址：Hash(key) = 11 \bmod 10 = 1 并将其进行存放：

不过由于该地址处已经存放了 key = 1 ，因此这两个 关键字 就发生了 哈希冲突 ，此时我们就可以将其称为 同义词； 若我们要对 key = 11 进行存放，我们就可以将其存放到其它还未存放关键字的地址中，如：

这里我们直接将其存放到地址 \textcolor{red}{2} 处；

• 最后我们再一次通过 哈希函数 确认了 key = 2 的 哈希地址：Hash(key) = 2 \bmod 10 = 2 并将其进行存放

若我们在存放 key = 2 之前，未存放 key = 11 那么 Hash(key) = 2 的位置处此时就是 空闲地址，因此我们可以直接将其存放到该地址处：

可以看到，不管是 key = 2 还是 key = 11 在 Hash(key) = 2 为 空闲地址 时，均可以进行存放； 对于 key = 1 而言，其 同义词 key = 11 可以存放到 Hash(key) = 2 处，其 非同义词 key = 2 也可存放到 Hash(key) = 2 处，因此我们称 空闲地址 既向 同义词 开放，又向 非同义词 开放；

1.2 聚集与堆积

在 哈希表 中，存在着 聚集现象 与 堆积现象。这两种现象均是指由于哈希冲突解决策略（特别是开放定址法）导致哈希表中出现连续被占用的区块，从而降低操作效率的情况。 下面我们将从4个维度来介绍这两种现象：

• 二者关系
  • 聚集现象 是一个 广义 的概念，指的就是 形成连续被占用区块的趋势；
  • 堆积现象 则是 聚集现象 的一种 具体表现形式，通常特指由 非同义词冲突 引发的 聚集
• 产生原因
  • 聚集现象 是由 同义词 或 非同义词 争夺后续 哈希地址 而产生的现象；
  • 堆积现象 则是由 非同义词 之间争夺 同一个后续哈希地址 而产生的现象；
• 核心机制
  • 聚集现象 的核心机制是因为 探测序列的规律性而导致的关键字在哈希表中扎堆；
  • 堆积现象 的核心机制是因为 两个关键字的探测序列相同而导致二者相互堵塞
• 包含关系
  • 聚集现象 包含 一次聚集、二次聚集 等多种类型
  • 堆积现象 则是通常被视为 二次聚集 的同义词，或 二次聚集 的典型结果

1.2.1 实例演示

聚集现象 的核心特征是：形成 连续 的被占用单元区块

就如上表中，连续的单元区块 1, 2, 3 被占用，此时我们就可以成 1, 2, 3 发生了 聚集现象 堆积现象 的核心特征是：形成了一条 很长的探测路径

当两个关键字的探测路径均为：（i + d_i)^2 时，就会发生 堆积现象

1.2.2 一次聚集于二次聚集

一次聚集 ：主要是由 线性探测法 引起。当发生冲突时，探测序列 是 固定步长（如依次检查下一个位置）。这会导致同义词以及被卷入的非同义词在哈希表中原点附近形成一个大的连续占用区块，就像堵车时车辆在路口排起长队。这是开放定址法中最常见也最需要避免的聚集类型 二次聚集：虽然采用了非固定步长的探测方法（如平方探测法），避免了“大区块”式的一次聚集。但如果两个不同的关键字（非同义词）的初始哈希地址相同，那么它们接下来的整个探测序列将完全一致。这导致这些关键字被“绑定”在同一条探测路径上，虽然不会形成很大的连续区块，但会使这条特定路径变得很长，后续落入此地址的关键字探测成本会增高

二、线性探测法

2.1 特点

线性探测法 也称 线性探测再散列法，它是 开放定址法 处理冲突策略的最常见的一种方法。 在 线性探测法 中，d_i=0,1,2,……,m-1。该方法的特点是：

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

即发生冲突时，每次往后探测相邻的下一个单元是否为空：

• 若为空，则将 关键字 插入到该位置
• 若非空，则继续往后查找： 当查找的位置为 m - 1 时，则下一次查找会从 0 位置处继续查找 当表中未被填满时，一定会存在一个空位供该关键字插入 当表中被填满时，查找的过程会回到 Hash(key) 处

2.2 插入

线性探测法 的 插入 过程并不难理解，可以分为两步：

• 通过 哈希函数 获取 哈希地址
• 判断当前位置是否发生冲突：
  • 发生冲突，继续向后查找，并重复执行判断
  • 未发生冲突，插入 关键字

这里我们通过具体的实例来说明整个 插入 的过程；

实例说明

现在我们需要对 [8, 10, 16, 20, 40, 50, 55, 60, 69, 77, 80, 85 进行 哈希存储，该 关键字序列 中有 12 个元素，因此我们需要准备一个长度为 L = 12 的数组作为 哈希表：

由于该表长为 合适 因此我们选择不大于表长的最大 质数 作为 除留余数法 的 模数。满足 \leq 12 的最大 质数 为 11，因此对应的 哈希函数 为：

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

• 插入 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) \bmod 12 = 6 \enspace {冲突} \ H_2 &= (5 + 2) \bmod 12 = 7 \enspace {冲突} \ H_3 &= (5 + 3) \bmod 12 = 8 \enspace {冲突} \ H_4 &= (5 + 4) \bmod 12 = 9 \enspace {冲突} \ H_5 &= (5 + 5) \bmod 12 = 10 \enspace {冲突} \ H_6 &= (5 + 6) \bmod 12 = 11 \enspace {不冲突} \end{align*} $$

通过 线性探测法 我们发现，当出现 6 次 冲突 后，我们在下标为 11 的 空闲地址，因此我们需要将 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) \bmod 12 = 0 \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) \bmod 12 = 4 \enspace {不冲突} \ \end{align*} $$

通过 线性探测法 我们发现，当出现 1 次 冲突 后，我们在下标为 4 的 空闲地址，因此我们需要将 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) \bmod 12 = 9 \enspace {冲突} \ H_2 &= (8 + 2) \bmod 12 = 10 \enspace {冲突} \ H_3 &= (8 + 3) \bmod 12 = 11 \enspace {冲突} \ H_4 &= (8 + 4) \bmod 12 = 0 \enspace {冲突} \ H_5 &= (8 + 5) \bmod 12 = 1 \enspace {冲突} \ H_6 &= (8 + 6) \bmod 12 = 2 \enspace {不冲突} \ \end{align*} $$

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

此时我们就完成了全部的插入过程。这里需要注意的是，因为我们是希望将元素插入到整个表中，因此这里我们使用的 m 不是 哈希函数 中使用的 质数 ，而是 实际表长；

2.3 查找

当我们对 哈希表 进行查找时，我们需要执行两步：

• 通过 散列函数 计算 散列地址
• 通过 关键字 对比进行 顺序查找
  • 遇到空时，查找失败
  • 回到 散列地址 时，查找失败
  • 找到 目标关键字 时，查找成功

也就是说，当 哈希表 中发生了 冲突 后，通过 线性探测法 处理冲突后，我们在进行查找的过程与 拉链法 一致，都是需要通过 顺序查找 完成； 不过对于查找失败时的判断，二者之间存在区别：

• 拉链法：查找到 空指针 时，查找失败
  • 哈希地址 对应的 链表 为 空链表
  • 对 链表 完成了查找，找到了最后的 空指针
• 线性探测法：根据 哈希表 的存储情况进行具体的判断：
  • 哈希表 已存满，则从 哈希地址 出发向后顺序查找，最后回到 哈希地址
  • 哈希表 未存满，则从 哈希地址 出发向后顺序查找，找到了 空闲地址

这里可能有朋友会有疑问——为什么 哈希表 未存满时，找到了 空闲地址 就代表 查找失败？ 这个问题其实很容易理解： 若我们需要在表中 插入 这个 关键字 那么此时找到的 空闲地址 就应该是该 关键字 插入的地址，因此当我们找到了这么一个 空闲地址 时，就表示 哈希表 中不存在该元素；

2.4 删除

当我们对使用了 开放定址法 处理冲突策略的 哈希表 进行 删除 操作时，我们不能向使用了 拉链法 的 哈希表 一样直接将 目标关键字 删除； 这是由于其 查找 操作的不同：

• 使用 拉链法 处理冲突的 哈希表 ，其 查找 操作实际上就是对 链表 进行查找
• 使用 开放定址法 处理冲突的 哈希表 ，其 查找 操作实际上就是对 循环数组 进行查找

正是因为这二者的性质不同，这就导致了其 查找失败 的条件也有区别：

• 拉链法：
  • 链表 为空表时，查找失败
  • 链表 中所有元素都被查找，仍为查找到 目标 时，查找失败
• 开放定址法
  • 循环数组 被填满时，从起始点开始查找，最后回到起始点时，查找失败
  • 循环数组 未被填满时，遇到 空闲地址时，查找失败

因此，若我们在使用了 开放定址法 的 哈希表 中直接删除元素，就会导致一个问题：

• 若 目标关键字 位于已删除的 关键字 后面，则我们无法通过 查找 操作找到目标关键字

这里我们以前面的例子进行说明，就比如我们要删除 key = 55 ，完成删除后，我们就得到了下表：

之后我们还要删除 key = 77 ，通过 哈希函数 我们可以得到该 关键字 的 哈希地址 为：Hash(key) = 77 \bmod 11 = 0 ； 由于此时该地址处为 空闲地址，根据其 查找 机制，我们就会得到一个结论——该表中没有 key = 77； 显然这个结论是错误的，因此为了避免出现这种问题，我们在对使用了 开放定址法 处理冲突策略的 哈希表 进行删除时，我们只能够采用 逻辑删除：

• 通过一个 删除标志 来标记已被 逻辑删除 的元素，而不直接进行 物理删除

这里我们还是采用刚才的例子，就比如我现在要删除 key = 55 ，那么我们可以通过一个 标记数组 来记录该元素的状态：

此时，若我们需要继续删除 key = 77 ，那么我们根据 哈希函数 获取的 哈希地址 Hash(key) = 77 \bmod 11 = 0 进行查找时，此时该位置已经存在 关键字 key = 55 ，因此接下来我们会继续向后进行 查找；

2.5 查找效率

由于 线性探测法 是在发生冲突时，依次往后寻找 空闲地址，这就导致了其最坏情况下 哈希表 会退化为 数组，即查找效率从 O(1) 退化到了 O(N)； 这是因为在最坏情况下，每一次的插入都会发生 冲突，而通过 线性探测法 处理冲突时：

• 冲突后再探测，关键字 一定是放在某个连续的位置

这就导致了 线性探测法 很容易造成同义词与非同义词的 聚集现象，严重影响查找效率。 因此通过 线性探测法 处理 哈希冲突 的 哈希表 ，其查找效率低下。

结语

在今天的内容中我们介绍了详细介绍了 开放定址法 的基本概念：

• 可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

了解了 聚集 与 堆积 这两种现象：

• 聚集现象 是指 形成连续被占用区块的趋势
• 堆积现象 是 聚集现象 的一种 具体表现形式

最后深入探讨了 线性探测法：

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

正是由于 线性探测法 的 固定步长探测序列 ，使得 同义词 与 非同义词 在 哈希表 中形成了一个很大的 连续占用区块，这就导致了 聚集现象 的发生，从而严重降低了 哈希表 的查找效率； 在下一篇内容中，我们将会了解第二种 开放定址法 —— 平方探测法。相比于 线性探测法 ，平方探测法 又是如何处理 哈希冲突 的呢？这个问题的答案，咱们将在下一篇内容中进行揭晓； 互动与分享

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

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