【数据结构】考研408 | 冲突解决精讲: 拉链法——链式存储的艺术与优化

导读

大家好，很高兴又和大家见面啦！！！ 在前面的内容中，我们共同确立了散列查找的核心思想：

• 通过哈希函数建立关键字与存储地址的直接映射，以期实现近乎 O(1)的查找效率。

我们认识到，这一高效策略的基石在于一个设计优良的哈希函数，但它也带来了一个不可回避的挑战——哈希冲突。 哈希函数 的构造我们介绍了4种构造方法：

• 直接定址法
• 除留余数法
• 数字分析法
• 平方取中法

但是无论 哈希函数 如何精巧，冲突在理论上终究无法完全避免。那么，当冲突不可避免地发生时，我们应当采取何种策略来妥善处理，从而保证哈希表的高效运作？ 这正是本篇所要解答的核心问题。我们将深入探讨一种极为经典且实用的冲突解决策略——拉链法。该方法以其直观的思想和灵活的应变能力，在实践中得到了广泛应用。 现在，让我们一同揭开 拉链法 的奥秘。

一、基本思想

拉链法是解决 哈希表 中 键冲突 的一种经典策略，其核心思想是将散列到同一位置的元素通过链表串联起来；

flowchart LR
	subgraph A[1]
		direction TB
		head1[head]
		a1[key1]
		b1[key2]
		c1[...]
		head1--->a1--->b1--->c1
	end
	subgraph B[2]
		direction TB
		head2[head]
		a2[key1]
		b2[key2]
		c2[...]
		head2--->a2--->b2--->c2
	end
	subgraph C[...]
	end
	A--->B--->C

如上图所示，当发生 冲突 时，拉链法 通过在 冲突地址 中创建一个 链表 ，通过该链表将所有的 同义词 连接起来； 不难发现，拉链法 就是 哈希表 与 链表 的一种组合应用：

• 在 哈希表 中通过 哈希函数 可以快速找到 关键字 的 哈希地址；
• 在 链表 中通过 查找 可以找到该地址下的所有 关键字

接下来我们就来一起了解一下该方法的 插入、查找、删除等基本操作；

二、插入

哈希表 的插入操作比较简单：

• 通过 哈希函数 确定 关键字 的 哈希地址
• 通过 哈希地址 将 关键字 插入到 链表

这里我们以关键字序列 [19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79] 为例来说明其具体的插入过程；

2.1 哈希函数

当前我们需要进行操作的 关键字序列 中存在 12 个元素，因此我们可以创建一个表长为 13 的 哈希表：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h1[0]
	 	h2[1]
	 	h3[2]
	 	h4[3]
	 	h5[4]
	 	h6[5]
	 	h7[6]
	 	h8[7]
	 	h9[8]
	 	h10[9]
	 	h11[10]
	 	h12[11]
	 	h13[12]
	end

这里我们可以通过 除留余数法 来构造 哈希函数，表长为 13 的 哈希表 ，不大于 13 的最大质数为 p = 13 ，因此这里我们选择 13 作为 模数，对应的 哈希函数 为：

2.2 哈希地址

为了简单一点，这里我们直接通过 哈希函数 获取该 关键字序列 中所有 关键字 对应的 哈希地址：

• Hash(19) = 19 \bmod 13 = 6
• Hash(14) = 14 \bmod 13 = 1
• Hash(23) = 23 \bmod 13 = 10
• Hash(01) = 01 \bmod 13 = 1
• Hash(68) = 68 \bmod 13 = 3
• Hash(20) = 20 \bmod 13 = 7
• Hash(84) = 84 \bmod 13 = 6
• Hash(27) = 27 \bmod 13 = 1
• Hash(55) = 55 \bmod 13 = 3
• Hash(11) = 11 \bmod 13 = 11
• Hash(10) = 10 \bmod 13 = 10
• Hash(79) = 79 \bmod 13 = 1

2.3 插入

通过 哈希函数 得到了 关键字 的 哈希地址 后，我们就需要将 关键字 插入到该地址对应的 链表 中； 链表 的插入有 头插法 与 尾插法，这里我们直接采取 头插法 依次插入 关键字：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h1[0]
	 	h2[1]
	 	h3[2]
	 	h4[3]
	 	h5[4]
	 	h6[5]
	 	h7[6]
	 	h8[7]
	 	h9[8]
	 	h10[9]
	 	h11[10]
	 	h12[11]
	 	h13[12]
	end
	h2 ---> k12[79] ---> k8[27] ---> k4[01] ---> k2[14]
	h4 ---> k9[55] ---> k5[68]
	h7 ---> k7[84] ---> k1[19]
	h8 ---> k6[20]
	h11 ---> k11[10] ---> k3[23]
	h12 ---> k10[11]

三、查找

在 拉链法 中，哈希表 的查找分为三步：

• 通过 哈希函数 确认 哈希地址
• 通过 哈希地址 找到 链表
• 通过 顺序查找 找 目标关键字
  • 找到 目标关键字 则查找成功
  • 未找到，则查找失败

就比如我们需要查找 key1 = 14、key2 = 25：

• 通过 哈希函数 确认 哈希地址 Hash(key1) = 14 \bmod 13 = 1 Hash(key2) = 25 \bmod 13 = 12
• 在链表中通过 顺序查找 找到 目标关键字 key1 在地址 Hash(key1) = 1 的链表中成功找到，查找成功 key2 在地址 Hash(key2) = 12 的链表中未找到，查找失败

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h1[0]
	 	h2[1]
	 	h3[2]
	 	h4[3]
	 	h5[4]
	 	h6[5]
	 	h7[6]
	 	h8[7]
	 	h9[8]
	 	h10[9]
	 	h11[10]
	 	h12[11]
	 	h13[12]
	end
	h2 ---> k12[79] ---> k8[27] ---> k4[01] ---> k2[14]
	h4 ---> k9[55] ---> k5[68]
	h7 ---> k7[84] ---> k1[19]
	h8 ---> k6[20]
	h11 ---> k11[10] ---> k3[23]
	h12 ---> k10[11]

classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class k2 R
class h13 R

四、删除

拉链法 的 删除 操作实际上就是 链表 的删除操作。其具体步骤如下：

• 通过 哈希函数 确认 哈希地址
• 通过 哈希地址 找到对应 链表
• 通过 顺序查找 找到 目标关键字
  • 找到 目标关键字 ，删除 该结点
  • 未找到，则不执行任何操作

比如这里我们需要删除 key1 = 01, key2 = 12 ，通过 哈希函数 我们可以确定 目标关键字 的 哈希地址：

• Hash(key1) = 01 \bmod 13 = 1
• Hash(key2) = 12 \bmod 13 12

确认了 哈希地址 后，我们可以找到 目标关键字 所在链表：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h2[1]
	 	h13[12]
	end
	h2 ---> k12[79] ---> k8[27] ---> k4[01] ---> k2[14]

classDef R color: white, fill: red, stroke: red, stroke-width: 2px

通过 顺序查找 查找，我们可以确定 目标关键字 是否存在链表中：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h2[1]
	 	h13[12]
	end
	h2 ---> k12[79] ---> k8[27] ---> k4[01] ---> k2[14]
	h13 ---> NULL
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class k4 R
class NULL R

从图中可以看到，key1 查找成功， key2 查找失败； 接下来，我们只需要对 key1 执行删除操作即可：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h2[1]
	 	h13[12]
	end
	h2 ---> k12[79] ---> k8[27] --->  k2[14]
	h13 ---> NULL
	k4[01] ---> k4`[释放结点空间内存]
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class k4 R

五、优缺点

拉链法 作为 哈希表 的一种非常实用的 哈希冲突 解决策略，它具有哪些优势和局限性呢？接下来，我们分别来探讨一下其优势与局限性；

5.1 优势

拉链法 通过 链表 来解决 哈希冲突 ，因此 链表 为其带来了以下优势：

• 动态适应性强：

由于链表节点是动态申请的，拉链法特别适合在建表之初无法确定记录总数的场景。数据可以随时增删，哈希表只需管理链表的增长，扩容的迫切性相对开放地址法要低。 这一点在介绍 链表 与 顺序表 时就有提到过，我就不再继续展开；

• 空间利用率高：

拉链法 允许 装填因子 大于1，这意味着数组空间可以比实际存储的记录数小，这在处理大规模数据时能节省可观的内存。特别是当记录本身尺寸很大时，指针带来的额外空间开销相对而言就变得微不足道了。 我们知道 装填因子 是由 已经存储的元素个数 以及 哈希表的长度 共同决定：

那么当我们选择用一个表长为 3 的哈希表来存储 [19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79] 这组 关键字序列 时，我们通过 哈希函数 ：

就得到了下图的哈希表：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h1[0]
	 	h2[1]
	 	h3[2]
	end
	h1 ---> k7[84] ---> k8[27]
	h2 ---> k1[19]  ---> k4[01]  ---> k9[55] ---> k11[10] ---> k12[79]
	h3 ---> k2[14] ---> k3[23] ---> k5[68] ---> k6[20] ---> k10[11]

classDef R color: white, fill: red, stroke: red, stroke-width: 2px

此时的 装填因子 ： \alpha = \frac{12}{3} = 4 > 1

• 避免堆积现象：

拉链法 只会将真正的 同义词 链接在一起，非同义词 绝不会发生冲突，这使得其平均查找长度通常较短。

堆积 简单的理解就是在 哈希表 中，当发生冲突时，若通过 线性探测法 来处理冲突，那么就会导致 同义词 聚集在某一块区域。 就比如这里我通过 哈希函数 Hash(key) = key \bmod 10 来存储 [1, 11, 21, 31, 41, 51, 61, 71, 2, 4] 这个 关键字序列，并且采用 线性探测法 来处理冲突，那么我们就会得到下面这个 哈希表：

可以看到，[11, 21, 31, 41, 51, 61, 71] 这些 关键字 通过 哈希函数 得到的 哈希地址 均为 Hash(key) = key \bmod 10 = 1 ，因此他们都会在 key = 1 插入到 哈希表 后发生冲突； 但是当我们使用的是 线性探测法 来处理冲突的话，就会导致这些 关键字 发生 聚集 ，这就使得在计算 [2, 4] 这两个 关键字 的 哈希地址 时，发生 二次冲突； 而 拉链法 则完全避免了这个问题，同义词 通过 链式存储 实现了全部存放在同一个 哈希地址 ，因此 非同义词 之间是完全不会发生任何 冲突；

PS: 线性探测法 会在后面的内容中详细介绍，这里大家简单了解即可

5.2 局限性与应对

拉链法也并非完美，其局限性主要体现在：

• 额外空间开销：

每个节点都需要额外的指针空间。当存储的节点规模本身很小时，这部分开销就显得比较突出。 这也是为什么在一些极致追求空间效率、且数据量小的场景下，开发者可能会考虑开放地址法。

• 缓存不友好与性能波动：

链表节点在内存中是随机分布的，这不如开放地址法将数据连续存储在数组中的局部性好，跳转访问会带来额外的时间开销。 同时，虽然 拉链法 平均性能优异，但若 哈希函数 设计不当，导致大量数据聚集在少数几个桶中，造成链表过长，性能会急剧下降。 拉链法 中我们将 哈希地址 称为 桶 ，通过 链表 链接起来的 同义词 就像是放入 桶 中的带有数字的乒乓球； 当 哈希函数 设计不当，导致某个 桶 中的乒乓球过多时，我们想要从 桶 中找到 目标乒乓球 的时间复杂度就会从 O(1) 退化到 O(N) ，这就相当于，我们使用的 数组 + 链表 的 哈希表 就直接退化为了 链表； 正是因为这种情况的存在，这就使得 拉链法 的性能不太稳定；

六、优化

正是因为 拉链法 存在 性能波动 的问题，因此我们可以对其进行进一步的 优化。其具体的优化思路可以分为两类：

• 优化 哈希函数：选择更合适的 哈希函数 从而保证 哈希表 的高效性
• 优化 链表：通过对 链表 进行优化，保证在 最坏情况 下的查找效率

这里我们主要介绍第二类——优化 链表

6.1 优化思路

优化 链表 的目的就是为了提高 链表 的查找效率，因此我们不能仅仅局限于 链表 ，而是要将 链表 视为 链式存储 的其中一种实现方式； 那也就是说，我们对 链表 进行的优化，实际上是对 链式存储 进行的优化。因此我们有以下几种优化方案：

• 初步优化：将 无序链表 优化为 有序链表
• 进阶优化：将 链表 优化为 二叉查找树
• 深度优化：将 二叉查找树 优化为 AVL 或 RBT

6.2 实例说明

这里我们还是以前面的例子为例，简单介绍一下 初步优化 的过程； 在 插入 操作中，将 同义词 有序插入到 链表 中，使其成为 有序链表：

flowchart LR
	subgraph A[哈希表]
	 	direction LR
	 	h1[0]
	 	h2[1]
	 	h3[2]
	 	h4[3]
	 	h5[4]
	 	h6[5]
	 	h7[6]
	 	h8[7]
	 	h9[8]
	 	h10[9]
	 	h11[10]
	 	h12[11]
	 	h13[12]
	end
	h2  ---> k4[01] ---> k2[14] ---> k8[27] ---> k12[79]
	h4 ---> k9[55] ---> k5[68]
	h7 ---> k1[19] ---> k7[84]
	h8 ---> k6[20]
	h11 ---> k11[10] ---> k3[23]
	h12 ---> k10[11]

当 链表 有序后，我们在查找的过程中，就可以通过判断 目标 关键字的范围，来初步提升查找效率； 当然在实际的应用中，我们更偏向于 深度优化，如 Java 中的HashMap 在链表长度超过一定阈值（如 8）时，会将其转换为 红黑树，以确保即使在最坏情况下，查找效率也能维持在 O(\log N)。

结语

在今天的内容中我们介绍了第一种解决冲突的方法——拉链法。下面我们就来一起回顾一下今天的内容： 基本思想 拉链法 作为解决 哈希冲突 的一种经典策略，其 核心思想 是：

• 将同一哈希地址的同义词通过链表链接

基本操作 采取 拉链法 解决冲突的哈希表，其基本操作实际上是对 链表 的操作：

• 插入：将 同义词 插入到 哈希地址 对应的 链表 中
• 查找：通过 哈希函数 找到 哈希地址，再通过 哈希地址 找到 链表，最后对 链表 进行 查找；
• 删除：通过 查找 操作找到 目标元素 ，再将 目标元素 从 链表 中 删除；

优缺点 正是因为 拉链法 采用的是 数组 + 链表 的组合，其优势与局限性均体现再 链表 上：

• 优势：
  • 动态适应性强
  • 空间利用率高
  • 避免堆积现象
• 局限性：
  • 额外空间开销
  • 缓存不友好与性能波动

优化思路 由于 拉链法 的 数组 + 链表 的组合，在 哈希函数 不合理的情况下会导致 哈希表 退化成 链表，因此我们的整体优化思路是 优化链式存储：

• 初步优化：将 无序链表 优化为 有序链表
• 进阶优化：将 链表 优化为 二叉查找树
• 深度优化：将 BST 优化为 AVL 或 RBT

拉链法 作为一项经典技术，其设计思想在 Java 的 HashMap 等现代数据结构中得到了实际应用和优化，展现了强大的生命力。 当然，冲突 的处理不仅仅可以使用 拉链法 ，在下一篇内容中，我们将会学习第二种 冲突 处理策略——开放定址法。具体内容我们会在下一篇内容中揭晓。 互动与分享

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

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