【数据结构】考研408 | 散列查找性能剖析：装填因子、冲突策略与优化全攻略

导读

大家好，很高兴又和大家见面啦！！！ 在前面的内容中我们以及认识了 哈希表 这个 高效查找 的数据结构；

• 哈希表 通过 哈希函数 将 关键字 映射成该 关键字 所对应的 哈希地址，从而实现通过 关键字 直接进行访问的 高效查找

在 哈希表 中，我们可以通过以下方式来构建一个 哈希函数：

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

在 哈希表 中，除了 直接定址法 会完全避免 哈希冲突 外，其它的方法均会存在无法避免的 哈希冲突； 因此当遇到 哈希冲突 时，我们可以通过两类策略来解决：

• 拉链法 ，又称为 链地址法，通过 链表 将 同义词 链接起来，从而解决 哈希冲突
• 开放定址法，在发生冲突时，通过在 哈希表 中探测 空闲地址 ，并将 同义词 插入到 空闲地址 中，从而处理 哈希冲突

哈希冲突 主要受 3 个因素的影响：

• 哈希函数：优质的 哈希函数 可以尽可能地降低冲突：
  • 如，在存储一段连续的 关键字 时，采用 直接定址法，可以直接避免 哈希冲突
• 冲突解决策略：当发生 冲突 时，选择合适的解决策略，能够有效降低冲突的发生
• 装填因子：装填因子 在不同的解决策略中，对 冲突 有着不同的影响

其中 哈希函数 对 哈希冲突 的影响主要体现在 其能否将关键字均匀地映射到整个哈希表的地址空间中 ； 这里我们以 除留余数法 为例，在该构造方法中，关键字 的分布情况与 模数 相关：

• 模数 与 关键字 互质，则 关键字 能够 均匀分布
• 模数 与 关键字 有 公因数 ，则 关键字 会出现 不均匀分布

因此我们在使用 除留余数法 时，需要选择一个 不大于表长的最大质数 作为 模数，来实现 关键字 的 均匀分布； 那么 冲突解决策略 以及 装填因子 又是如何影响 哈希冲突 的呢？从今天的内容开始，我们会深入探讨这三者之间的关系。下面就让我们直接进入正题吧；

一、装填因子

1.1 定义

装填因子 是 衡量散列表（哈希表）空间使用情况和性能表现的一个关键指标。一般记为 \alpha ，定义为一个表的 装满程度 ，即：

哈希表 的 平均查找长度 ASL 依赖于 哈希表 的 装填因子 {\alpha} ，而不直接依赖于 n 或 m 。直观点看：

• \alpha 越大，表示装填的记录 越“满” ，发生 冲突 的可能性越大
• \alpha 越小，表示装填的记录 越“空” ，发生 冲突 的可能性月小

1.2 实例说明

这里我们简单的说明一下 哈希表 的 满 和 空：

就比如在上表中，此时 哈希表 中还未 装填 任何 关键字 ，因此 表中记录数 n = 0 ，该 哈希表 的长度为 m = 11 ，那么我们通过 \frac{n}{m} 获取的 装填因子 \alpha = \frac{0}{11} = 0 ，此时的 哈希表 为 空表 ，因此，无论我们接下来插入的 关键字 是什么，都不会发生 冲突； 当我们通过 除留余数法 来构造 哈希函数 时，我们可以构造 Hash(key) = key \bmod 11 这个 哈希函数 来实现 关键字 的 均匀分布； 这里我们以 关键字序列 ：[19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10] 以及 线性探测法 为例，进一步说明； 当该序列中的已经有 8 个及以上的 关键字 完成装填后，如下所示：

此时该表的 装填因子 为 \alpha = \frac{n}{m} = \frac{8}{11} \approx 0.73 ，这就代表着 哈希表 已经快装 “满” 了，在这种情况下就很容易发生 冲突 ，最直观的说法就是：

• 当插入的 关键字 的余数不是 剩余 空位对应的余数时，那就一定会发生冲突

比如，这里我们选择插入一个新元素 79 ，通过 哈希函数 可知 Hash(key) = 79 \bmod 11 = 2 ，通过查表可知，当前从 2 \sim 5 这大块的连续区域都已经 装填 了 关键字 ，因此在我们探测到 6 这个位置前，均会发生 哈希冲突 ； 若此时 关键字序列 中的所有元素均完成 装填 ：

此时对应的 装填因子 ：\alpha = \frac{n}{m} = \frac{11}{11} = 1 ，这时的 哈希表 属于 满表 的状态，现在我们无论插入任何一个新的 关键字 ，均会发生 哈希冲突； 从这个例子我们就可以简单的体会到 装填因子 对 哈希冲突 的影响； 但是不同的 冲突解决策略 中，装填因子 对 哈希冲突 的影响又不相同，接下来我们就来一起探讨一下；

二、拉链法

在 拉链法 中，当发生冲突时，我们是通过 链表 链接 同义词 的方式来解决 哈希冲突 ，这里我们还是以上面的例子为例进行说明； 对于 关键字序列 ：[19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10] 当我们采用 拉链法 解决冲突时，我们便会得到下面这个 哈希表：

flowchart LR
	subgraph Hash[哈希表]
		direction LR
		a[0]
		b[1]
		c[2]
		d[3]
		e[4]
		f[5]
		g[6]
		h[7]
		i[8]
		j[9]
		k[10]
	end
	a ---> k9[55] ---> k10[11]
	b ---> k3[23] ---> k4[01]
	c ---> key5[68]
	d ---> k2[14]
	f ---> k8[27]
	h ---> k7[84]
	i ---> k1[19]
	j ---> k6[20]
	k ---> k11[10]

此时，虽然该表的 装填因子 \alpha = \frac{n}{m} = \frac{11}{11} = 1 ，但是通过观察我们不难发现，此时若我们插入的元素对于的 哈希地址 为 4、6 这二者中的一个的话，仍然不会发生 哈希冲突 ； 因此 装填因子 在 拉链法 中并不能在 0 \sim 1 这个范围内准确的反映 哈希冲突 的概率； 那么现在问题来了，既然 拉链法 中，装填因子 无法反映 哈希冲突 的概率，那么它具体反映的是什么呢？ 这里我们直接给出结论—— 装填因子 反映的是 链表的平均长度。简单的说就是：

• 当 \alpha = 1 时，说明 哈希表 中各个 桶 中 链表 的 平均表长 为 1

因此 拉链法 中，装填因子 的值是允许 大于 {1}。这里我们还是以上述的 关键字序列 为例，但是我们将 哈希函数 更改一下，如 Hash(key) = key \bmod 5 ，此时我们得到的 哈希表 如下所示：

flowchart LR
	subgraph Hash[哈希表]
		direction LR
		a[0]
		b[1]
		c[2]
		d[3]
		e[4]
	end
	a ---> k6[20] ---> k9[55] --->  k11[10]
	b ---> k4[01] ---> k10[11]
	c ---> k8[27]
	d  ---> k3[23] ---> key5[68]
	e ---> k1[19] ---> k2[14] ---> k7[84]

此时的 装填因子 \alpha = \frac{n}{m} = \frac{11}{5} = 2.2 ，从图中我们也不难发现，每个 桶 对应的 链表 的 平均表长 为 2。 因此我们说 装填因子 在 拉链法 这种 冲突处理策略 下，主要反映的是 链表的平均表长；

三、开放定址法

在 开放定址法 这种 冲突处理策略 下，在发生冲突时，我们则是通过 探测 表中的 空闲地址 的方式来处理冲突。因此一个 哈希表 能够 装填 的 关键字 个数，取决于 哈希表的长度。这样我们就不难得出一个结论：

即 装填因子 直接反映了 冲突的概率； 简单的理解就是：

• 装填因子 越接近 0 ，说明表中的 空闲地址 越多，发生 冲突 的概率越小
• 装填因子 越接近 1 ，说明表中的 空闲地址 越少，发生 冲突 的概率越大

理解了 装填因子 对不同的 冲突处理策略 的影响后，接下来我们就需要进一步探讨他们是如何影响一个 哈希表 的性能；

四、性能分析

4.1 拉链法

在 拉链法 中，由于 装填因子 反映的是 平均链表长度 ，因此我们不难得出结论：

• 装填因子 越大，哈希表 的 平均链表长度 越长
• 装填因子 越小，哈希表 的 平均链表长度 越短

而 链表 的 链表长度 又直接反映的 链表 的 查找效率：

• 链表 越长，对应的 查找效率 越低
• 链表 越短，对应的 查找效率 越高

由于 链表 的 时间复杂度 为 O(N) 这个数量级，那么我们不难得到不同长度的链表对应的 比较次数：

下面我们就通过分析 关键字序列 ：[19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10] 在两种 哈希函数 下对应的 ASL；

ASL: $Hash(key) = key \bmod 11$

当我们通过 哈希函数 Hash(key) = key \bmod 11 来获取 哈希映射 时，各 关键字 在查找的过程中，其比较次数依次如下所示：

其 平均查找长度 为：

$$ \begin{align*} ASL &= \sum\limits^{n}_{i = 1}p_ic_i \ ASL &= \frac{1 * 9 + 2 * 2}{11} \ ASL &= \frac{13}{11} \approx 1.18 \end{align*} $$

ASL: $Hash(key) = key \bmod 5$

当我们通过 哈希函数 Hash(key) = key \bmod 5 来获取 哈希映射 时，各 关键字 在查找的过程中，其比较次数依次如下所示：

其 平均查找长度 为：

$$ \begin{align*} ASL &= \sum\limits^{n}_{i = 1}p_ic_i \ ASL &= \frac{1 * 5 + 2 * 4 + 3 * 2}{11} \ ASL &= \frac{19}{11} \approx 1.73 \end{align*} $$

小结

在 拉链法 中当 \alpha 反映的是 链表的平均长度 ，从上面的两种情况来看，我们不难得到以下结论：

• 链表平均长度 越长，查找效率越低
• 链表平均长度 越短，查找效率越高

4.2 开放地址法

在 开放定址法 中，我们有介绍了 4 种方法：

• 线性探测法：当发生冲突时，以 固定探测步长 1 ，在表中进行 循环探测
• 平方探测法：当发生冲突时，以 平方跳跃探测步长 \pm i^2，在表中进行 循环探测
• 伪随机序列法：当发生冲突时，以 伪随机数生成器 生成的 伪随机序列 为步长，在表中进行 循环探测
• 双散列法：当发生冲突时，以 第二个散列函数 为 关键字 获取一个 专属探测步长，在表中进行 循环探测

不管是哪种方法，其基本原理都是一致的：

• 通过在 哈希表 中 探测空闲地址 来解决冲突

因此我们这里就以最简单的 线性探测法 以及 平方探测法 为例，来分析 开放定址法 的性能；

线性探测法

当我们通过 哈希函数 Hash(key) = key \bmod 11 来获取 哈希映射 时，线性探测法 处理冲突时，对应的 哈希表 如下所示：

各 关键字 在 插入 的过程中对应的 装填因子 以及 冲突 次数依次为：

各 关键字 在查找的过程中，其比较次数依次如下所示：

其 平均查找长度 为：

$$ \begin{align*} ASL &= \sum\limits^{n}_{i = 1}p_ic_i \ ASL &= \frac{1 * 8 + 2 * 1 + 3 * 1 + 7 * 1}{11} \ ASL &= \frac{20}{11} \approx 1.82 \end{align*} $$

平方探测法

当我们通过 哈希函数 Hash(key) = key \bmod 11 来获取 哈希映射 时，线性探测法 处理冲突时，对应的 哈希表 如下所示：

各 关键字 在 插入 的过程中对应的 装填因子 以及 冲突 次数依次为：

各 关键字 在查找的过程中，其比较次数依次如下所示：

其 平均查找长度 为：

$$ \begin{align*} ASL &= \sum\limits^{n}_{i = 1}p_ic_i \ ASL &= \frac{1 * 7 + 2 * 1 + 3 * 1 + 4 * 1 + 8 * 1}{11} \ ASL &= \frac{24}{11} \approx 2.18 \end{align*} $$

小结

在 开放定址法 中 装填因子 反映的是 冲突的概率。

从上面的介绍中我们不难发现，随着 装填因子 的增大，冲突的次数 也有增加：

• 当 \alpha \geq 0.8 时，冲突的次数会明显增加： 如 线性探测法 中，\alpha = 0.82 时发生冲突，此时的冲突次数为 6 平方探测法 中，\alpha = 0.91 时发生冲突，此时的冲突次数为 7

因此我们可以得到结论：

• 装填因子 越大，开放定址法 的查找效率越低
• 装填因子 越小，开放定址法 的查找效率越高

4.3 性能优化

由于 哈希表 的性能直接由 装填因子 反映，因此在 哈希函数 相同的情况下，不同的 冲突解决策略 的优化思路也不相同：

• 拉链法 中，装填因子 反映的是 平均链表长度 ，因此对 拉链法 进行优化时，主要是优化 平均链表长度
• 开放定址法 中，装填因子 反映的是 冲突的概率，因此对 开放定址法 进行优化时，主要是优化 冲突的概率

拉链法优化

对于 查找效率 为 O(N) 的 链表 而言，其优化方向为：

• 减少 链表 的长度

因此我们可以通过设置一个阈值，如当链表长度到达 L 时，我们通过相应的优化方案来减少 链表 的长度：

• 使用一个更大的 哈希表 ，对表中的 关键字 通过 再哈希 将其映射到 新的哈希表 中，以此来达到 减少链表长度 的目的
• 通过将 链表 的 线性结构 优化为 树形结构，如 AVL、RBT 使其 查找效率 从 O(N) 下降到 O(\log N)

开放定址法优化

对于 开放定址法 而言，由于其 哈希冲突 的概率与 装填因子 密切相关，因此我们不妨设置一个阈值，如 \alpha = 0.7 ，当我们在 插入操作 的过程中，发现此时的 哈希表 的 装填因子 达到这个阈值时，我们就需要通过 扩容操作 ，使用一个 更大的哈希表 来降低 装填因子 ，以此来降低 哈希冲突 的发生概率； 这里的 扩容操作 也称为 再哈希法，即当 哈希表 的 装填因子 到达预先设定的 扩容阈值 时，通过申请一块更大的表长为 质数 的 哈希表 ，借助新表对应的 新哈希函数 ，将原表中的关键字再哈希到新表中 ，以此来达到 降低装填因子 的目的；

小结

优化哈希表的关键在于 明智地管理装填因子：

• 对于开放定址法，需要保守一些，保持较小的装填因子（如 0.5 \leq \alpha \leq 0.75）；
• 对于 拉链法，则可以更激进一些，允许较大的装填因子（如 0.75 \leq \alpha \leq 1.0）

当 装填因子 达到相应的阈值时，通过 动态扩容 和 可能的链表树化 来维持高性能 当我们选择 动态扩容 的 在哈希法 时，实际上就是 通过空间换时间 ，以牺牲更多的空间来维持高性能的过程； 在 Java 8 的 HashMap 中则采用的是 链表树化 的方式，以保证在 最坏情况 下仍有 较好的查询效率；

结语

在今天的内容中我们介绍了 哈希表的性能 的相关知识点。哈希表 的性能与 装填因子 密切相关：

• 在相同的 哈希函数 下，使用 开放定址法 处理冲突策略时：
  • 装填因子 越大，哈希表 发生 冲突 的概率越高
  • 装填因子 越小，哈希表 发生 冲突 的概率越低
• 在相同的 哈希函数 下，使用 拉链法 处理冲突策略时：
  • 装填因子 越大，链表 的 平均长度 越长
  • 装填因子 越小，链表 的 平均长度 越短

因此，为了维持 哈希表 的 高性能 ，我们可以采用 再哈希法 这种 动态扩容 操作，以 空间换时间 的方式，来达到维持 较小的装填因子 的目的； 对于使用了 拉链法 处理冲突策略的 哈希表 ，我们还可以采用 链表树化 的方式，来维持 最坏情况下 的 查找效率； 回顾整个 哈希表 章节，我们从其 基本思想​ 出发，学习了多种 哈希函数构造方法，深入分析了 拉链法​ 与四种 开放定址法​ 这两种核心的冲突解决策略，并最终落脚于本章的 性能分析与优化。哈希表的精髓在于通过巧妙的映射，在平均情况下实现接近 O(1) 的高效查找，其性能是 哈希函数、冲突策略 与 装填因子 三者共同作用的结果。 掌握了 高效的查找技术 之后，我们的学习之旅将进入【数据结构与算法】的另一个核心领域——排序。 有序的数据不仅能提升查找效率（如二分查找），其本身也是许多 复杂算法 和 数据处理流程 的基础。在接下来的章节中，我们将一同探索各类排序算法的奥秘，从直观的冒泡排序到高效的快速排序、归并排序，理解它们的思想、实现与性能差异。 敬请期待，我们 排序 章节再见！ 互动与分享

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

感谢您的耐心阅读！我们下一篇再见！