【数据结构】考研408 | 散列函数构造精解：从直接定址到平方取中的原理、场景与实战权衡

(散列函数)

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇关于散列查找的探讨中，我们共同揭开了 哈希表（散列表）这一高效数据结构的神秘面纱。 我们了解到，其接近 O(1)​ 级查找性能的核心，在于它通过一个精巧的哈希函数，在关键字与存储地址之间建立了直接的映射关系，从而跳过了传统查找中逐次比较的过程。 我们深入分析了 哈希表 的构造思想与不可避免的 哈希冲突 现象，并认识到：

• 一个设计精良的哈希函数，正是减少冲突、保证效率的基石。它如同整个体系的“调度中心”，其质量直接决定了哈希表性能的优劣。

那么，如何设计一个优秀的哈希函数？这正是本篇将要解答的核心问题。 我们将系统剖析四种经典的构造方法：

• 从最直观的直接定址法，到应用最广、蕴含数理之美的除留余数法，再到针对特定数据模式的数字分析法与平方取中法，揭示它们背后的设计智慧、适用场景与权衡之道。

理解这些方法的原理，便是掌握了为数据规划高效存储路径的蓝图。现在，让我们一同深入探索，学习如何为不同的数据特性，量身打造最合适的 哈希函数。

一、构造思想

在构造 哈希函数 时，必须注意以下几点：

• 哈希函数 的定义域必须包含 全部关键字，而值域的范围则依赖于 哈希表的大小
• 哈希函数 计算出的地址应尽可能 均匀地分布 在整个地址空间，尽可能地减少冲突
• 哈希函数 应尽可能的简单，能在较短的时间内计算出任意一个 关键字 对应的 哈希地址

在 哈希表 中常有四种 哈希函数 的构造方法：

• 直接定址法——H(key)= key或H(key)=a*key+b
• 除留余数法——H(key)=key%p
• 数字分析法——选取数码分布较为均匀的若干位作为散列地址
• 平方取中法——取关键字的平方值的中间记为作为散列地址

接下来我们将会逐一探讨这些方法的构造思路、适用场景以及优缺点；

二、直接定址法

直接定址法 是指 直接取关键字的某个线性函数值作为散列地址，对应的散列函数为：

$$ \begin{align} Hash(key) &= key \ {或} \enspace Hash(key) &= a * key + b \end{align} $$

其中，a 和 b 是常数。 这种方法计算最简单，且 不会产生冲突 。它 适合关键字的分布基本连续的情况。 就比如存储 [1, 2, 3, 4, 5, 6] 这些关键字，当我们采取该方法时，我们只需要申请长度为 L = 7 的 哈希表 空间，这里我们直接使用 Hash(key) = key 来进行 哈希映射 ，这样我们就得到了下面这份 哈希表：

可以看到，此时不管是 插入、删除、查找，其效率均为 O(1)。

若关键字分布不连续，空位较多，则会造成存储空间的浪费。

就比如存储 [1, 3, 5, 7, 15]

此时我们会发现，虽然其 插入、删除、查找 的效率仍最优，但是其空间利用率也大大降低；

三、除留余数法

除留余数法 是指 在表长为 m 的哈希表中，取一个不大于但接近或等于 m 的最大质数 p ，通过取余的方式将 关键字 转换为 哈希地址。其 哈希函数 为：

就比如：

• 哈希表长为 13 时，哈希函数为H(key)=key %13
• 哈希表长为 15 时，哈希函数为H(key)=key %13

这里可能有朋友会好奇，为什么 哈希表 长度为 15 时，也使用的是 13 而不是表长 15？ 这是因为 13 是不大于 15 的最大质数。 这时可能有朋友又会有疑问，为什么一定要选用质数？ 在《数论》中有提到过，用质数取模可以让数据在哈希表中分部的更均匀，冲突更少。 下面我们就来详细的探讨一下这个问题；

3.1 影响冲突因素

冲突 是指 两个或两个以上的关键字通过哈希函数映射到了同一地址； 在 除留余数法 中，我们是通过判断 关键字 \bm{key} 与 模数 \bm{p} 的 余数 \bm{r} 是否相同，进而判断是否会发生 冲突：

• 余数相同，则发生冲突
• 余数不同，则不发生冲突

接下来我们就来一起探讨一下 余数；

3.1.1 余数

余数是整数除法中的基本概念，它表示在平均分配时无法被整除而剩余的部分。 在计算机领域中，我们可以通过取模运算 \bmod 来直接获取 余数：

而在数学领域中，我们则是通过除法运算 \div 来获取余数：

取模运算 实际上就是 只取余数 的 除法运算，因此我们想要获取 余数 与 模数 以及 被模数 之间的关系，就需要借助 除法运算。

在除法运算中，我们可以将余数表示为：r = a - b * c，且余数的取值范围是 0 \leq r \leq b - 1 ，即 余数一定是不小于0，且一定小于除数的整数 在 除留余数法 中，关键字 \bm{key} 就是 被除数，模数 \bm{p} 就是 除数，因此二者的 余数 \bm{r} 可以表示为 \bm{r = key - p * k}, (k \in N) 且 \bm{r} 一定满足 0 \leq r \leq p - 1；

3.1.2 因数

因数是数学中描述整数之间整除关系的一个基本概念：

• 若整数 a 除以整数 b（b ≠ 0）的商正好是整数且余数为零，则称 b 是 a 的因数

根据因数的定义，我们可以将其概括为，在整数除法：a \div b = c \cdots r，若 r = 0 则称整数 b 为整数 a 的因数； 又或者说，当 b * c = a 时，我们可以称 b 为 a 的因数，同理 c 也是 a 的因数； 也就是说，当整数 a 存在一个因数 b 时，那它一定也存在一个因数 c ，且该因数满足 c * b = a

3.1.3 余数与因数

由上述内容可知，对于任一 模数 p ，我们假设它有多个 因数，且其中一个 因数 为 a。 当我们要存储的 关键字 key 是这些 因数 中其中一个（如因数 \bm{a}）的倍数时，我们可以将该关键字表示为 key = n * a；

PS：这里我们也可以称 a 为 模数 p 与 关键字 key 的公因数。

此时我们将其带入到上述的关系式，就得到了：

$$ \begin{align*} r &= key - p * k \ r &= n * a - p * k \end{align*} $$

由于 a 为 模数 的 因数，因此我们可以将 模数 表示为：m * a ，这样我们就得到了 余数 与 因数 之间的关系：

$$ \begin{align*} r &= n * a - p * k \ r &= n * a - m * a * k \ r &= (n - m * k) * a \end{align*} $$

这也就是说，当我们插入的 关键字 是 模数 的某个 因数 的倍数时，那么我们算得的 余数 一定是该 因数 的倍数，并且其值满足：

这也就表明，当范围内存在的 因数 \bm{a} 的 倍数 个数越少，发生冲突的概率就越高； 这样我们就得到了结论：

• 在 除留余数法 中，冲突 与 模数 \bm{p} 在 [0, p - 1] 这个范围内，其 因数 的 倍数 的个数有关： 范围内，因数 的 倍数 的个数越多，冲突的概率越小 范围内，因数 的 倍数 的个数越少，冲突的概率越高

3.1.4 思维陷阱

看到这个 余数 与 因数 之间的关系式：r = (n - m * k) * a 时，有朋友可能会说，你这里的 m 不同样是 模数 p 的一个 因数 吗？ 就比如 12 = 3 * 4 你这里只不过把其中一个 因数 作为公因数提出来了，这才得到的 r = (n - m * k) * a ，那我为什么一定要说是 r 与 a 的关系，而不是与 m 这个 因数 之间的关系呢？ 这个问题的答案很简单，因此此时我们陷入了一个 思维陷阱 ，我们从 余数 与 关键字 之间的关系转变为了 余数 与 因数 之间的关系； 就像这里说的，对于 模数 而言，不管是 m 还是 a 均为其 因数 ，那么我们最后为什么将其转变为了 r 与 a 而不是 r 与 m 呢? 这个视角的切换实际上是由 关键字 决定的。因为对于 关键字 和 模数 而言，a 这个因数是他们二者的 公因数 ，而 n/m 则可以视为这个 公因数 分别对应的两个 倍数； 因此我们在看待 r = (n - m * k) * a 这个关系式时，我们应该将其视为：

• 余数r = （倍数n - 倍数m * 倍数k）* 因数a

也就是括号中的内容全是 倍数。而不是将其视为：

• 余数r = （倍数n - 因数m * 倍数k）* 因数a

就拿前面的例子 12 = 3 * 4 来说明，对于 模数 12 而言，当我们将 3 作为 因数 时，这里的 4 我们就要将其视为 3 的倍数，而不是 12 的因数；同理，当我们将 4 视为 因数 时，那么 3 就时 4 的 倍数 ，而不是 12 的因数； 这个问题看似不起眼，实际上这也是我之前陷入的一个误区，因此我在这里给大家分享一下；

3.1.5 步长

这里我们要引入一个新概念——步长； 所谓的 步长 ，我们可以将其视为 变化量。这就好比 1, 2 这两个关键字的步长为 1； 在前面的探讨中，我们发现了在 [0, p-1] 这个范围内，冲突与 p 的 因数 之间的关系：

• 范围内，因数 的倍数个数越多，冲突发生的概率越低
• 范围内，因数 的倍数个数越少，冲突发生的概率越高

若是引入 步长 的概念，我们再来看这个问题； 当我们将 因数 \bm{a} 及其倍数视为一个 因数序列 ，我们会发现，该序列是一个 步长 为 \bm{a} 的等差数列； 而要发生冲突的前提是 两个关键字的余数相同，若我们将这些发生 冲突 的关键字组成一个 冲突序列，这里我们以 模数 3 为例，我们会得到 3 个 冲突序列 ，该 模数 对应的冲突序列为：

• 余数为 0 的冲突序列：[0, 3, 6, 9, \cdots]
• 余数为 1 的冲突序列：[1, 4, 7, 10, \cdots]
• 余数为 2 的冲突序列：[2, 5, 8, 11, \cdots]

不难发现，每一个冲突序列均是 步长 为 \bm{3} 的等差序列； 因此我们可以得到一个结论：

• 当两个 关键字 的差值为 模数 的倍数时，必然发生冲突

3.2 不均匀分布

不均匀分布 指的是数据未能均匀地分散到所有可用的位置； 简单的说就是，当 关键字序列 中的数据与模数存在 公因数 \bm{a} 时，关键字 会集中分布在 [0, p-1] 这个范围内 \bm{a} 的倍数上； 如 模数 为 12 ，若关键字与 12 有 公因数3 那么，该关键字一定是分布在 [0, 3, 6, 9] 这些位置上； 若 公因数a = 1 ，在 [0, p-1] 这个范围内的所有位置均为 1 的倍数，因此 关键字 会分布在该范围内的所有位置上，这种情况就称为 均匀分布； 因此 不均匀分布 可以解释为 关键字与模数存在公因数a 且 a \neq 1 时，关键字的分布情况

3.3 质数与合数对比

3.3.1 基本定义

质数 与 合数 是数学中重要的基础概念：

• 质数 （Prime number）也称 素数：一个大于1的自然数，如果它除了 1 和它自身之外，无法被其他任何自然数整除，那么这个数就称为 质数
• 合数 （Composite Number）也称 合成数：一个大于1的自然数，如果它除了1和它自身之外，还能被其他自然数整除，那么这个数就称为 合数

3.3.2 模数的选择

由这二者的定义可知：

• 质数 是有且仅有 \bm{1} 与 它本身 两个 因数 的自然数
• 合数 是至少有 \bm{4} 个 因数 的自然数

从是否均匀分布的角度来看：

• 若选择 质数 作为 模数 ，那么 关键字key 与 模数p 的 公因数a 有且仅有两种情况： a = 1 ，此时 关键字 会 均匀分布 a = p ，此时 关键字 会 不均匀分布 在 Hash(key) = 0 处
• 若选择 合数 作为 模数，那么 关键字key 与 模数p 的公因数a 至少有3种情况： a = 1 ，此时 关键字 会 均匀分布 a = p ，此时 关键字 会 不均匀分布 在 Hash(key) = 0 处 1 \neq a \neq p ，此时 关键字 会分布在 因数序列 [0, a, 2a, \cdots] 处

在实际应用中，我们无法预知所有关键字的数学特性，因此选择 质数 作为 模数是一种 更为稳健和安全的设计选择；

3.4 实例验证

为了帮助大家更加清晰的看到 合数 与 质数 的区别，这里我们以一个随机序列 [1,3,6,8,9,13,15,22,30,35,36,42,47,50,56] 为例，进行说明。 在这个长度 L = 15 的序列中，我们分别以选择 13 以及 15 作为模数，来观察这组序列中的元素的分布情况：

• 选择 13 作为 模数

• 选择 15 作为 模数

若我们通过发生冲突的次数，我们会发现 13 作为模数时，发生冲突的次数更多，而 15 作为模数时，发生冲突的次数更少； 但是我们以发生冲突的位置再进行观察：

• 选择 13 作为模数，冲突发生在步长为 13 的 冲突序列 中
• 选择 15 作为模数，冲突发生在步长为 5 以及步长为 3 的 因数序列 中

由于 冲突 发生时，对应的 同义词 所组成的 冲突序列 的步长一定为 模数 p，因此这里我仅讨论这二者的 因数序列；

• 模数 13 有两个因数序列： 因数1：[0,1,2,3,4,5,6,7,8,9,10,11,12] 因数13：[0]
• 模数15 有四个 因数序列： 因数1：[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] 因数15：[0] 因数3: [0,3,6,9,12] 因数5: [0,5,10]

若我们仅看除了 因数 1 以外的其它 因数序列 ：

• 选择 13 作为 模数

• 选择 15 作为 模数

我们不难发现，这组随机序列中，15 发生冲突的概率明显要高于 13 中发生冲突的概率； 当然，有朋友会说，你这里的例子中 13 的倍数这么少，当然会这样了。当你也存在这个疑惑时，那么恭喜你，你即将真正的掌握 除留余数法； 首先，我需要说明，没错，这里会造成 15 为模数，按照位置观察时发生的冲突概率高正是因为数据中存在着 15 的两个因数 3/5 的倍数多； 但也正是因为这个原因，我们才更需要选择 质数 作为 模数。从客观因素来看：

• 质数仅存在 1 和 它本身 ，因此很难遇到全是 p 的倍数的情况，若真正遇到了，我们则需要进行相应的调整
• 合数 因为存在多个 因数，这使得数据中存在其 因数 的倍数的概率大大增加，因此更容易在 因数序列 中出现冲突；

从主观上来看，正是因为 合数 的多 因数 而导致发生 不均匀分布 的概率较高，所以我们需要选择 质数 作为 模数 来减少这种 不均匀分布 的概率；

四、数字分析法

数字分析法是指通过分析数字的规律，选取数码分布均匀的若干位作为哈希地址； 设关键字是 r 进制数（如十进制数），而 r 个数码在各位上出现的频率不一定相同：

• 在某些位上分布均匀一些，每种数码出现的机会均等；
• 在某些位上分布不均匀，只有某几种数码经常出现

此时可选取数码分布均匀的若干位作为哈希地址。 这里我们以学号为例，正常情况下，学生的学号是以下面的格式进行编码：

• 入学年份 + 学校/学院代码 + 专业/系部代码 + 班级序号 + 个人序号 + 层次/学制代码 + 性别标识

就比如学号：2021 001 4 11408 12 01 1 ，各部分对应的数码分别为：

• 入学年份：2021
• 学校代码：001
• 层次/学制代码：4
• 专业：11408
• 班级序号：12
• 个人序号：01
• 性别：1

根据不同的视角，我们可以创建不同的 哈希函数，就比如：

• 以整个学校的视角：Hash(key) = 年份 + 学制 + 专业 + 班级 + 个人序号 + 性别
• 以专业视角：Hash(key) = 年份 + 班级 + 个人序号 + 性别
• 以班级视角：Hash(key) = 个人序号 + 性别

这里我们以班级视角为例：

• 在同一个班级中，入学年份、学校代码、学制、专业、班级这些部分的数码都是固定的，即数码的分布不均匀
• 个人序号、性别这些是不固定的，即数码分布均匀

因此我们在以班级的视角构建 哈希函数 时，则需要舍去分布不均匀的部分，而选择分布均匀的部分作为 哈希地址； 这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

五、平方取中法

平方取中法 是指 取关键字的平方值的中间几位作为哈希地址； 就比如现在有一组关键字集合，每一个关键字均由3部分组成：

• 首部：[0,2,9]
• 中部：[0,1,8]
• 尾部：[0,1,5]

这里我们可以看到，这些关键字的每一位上的数码的分布都不均匀，在这种情况下，我们就可以借助 平方取中法 来构建一个 哈希函数：

$$ \begin{array}{lr} &985 \ & \underline{{*} \phantom{000}985} \ &\textcolor{red}{49}25 \ &7\textcolor{red}{88}0 \phantom{0} \ &\underline{\phantom{0}88\textcolor{red}{65} \phantom{00}} \ &97\textcolor{red}{02}25 \end{array} $$

就比如这里，我们对关键字 key = 985 通过 平方取中法 获取 哈希地址，具体取多少位要视实际情况而定。 这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀：

• 就比如上述的例子中，我们选取了中间两位，通过标红的数位可以看到，平方后的中间两位是由关键字 985 的每一位数字运算得来： 985 * 5 = \phantom{00}\textcolor{red}{49}25 985 * 8 = \phantom{0}7\textcolor{red}{88}0 985 * 9 = 88\textcolor{red}{65}

因此该方法适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。 在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说明哪种散列函数更好。在实际选择中，采用何种构造散列函数地方法取决于关键字集合地情况。

结语

在今天的内容中，我们对 散列函数（哈希函数）的构造方法进行了系统且深入的讲解。接下来就让我回顾一下今天的重点内容： 🔍 核心构造方法回顾

🚀 下篇内容预告 尽管精心设计的散列函数能有效减少冲突，但无法完全避免。在下一篇博客中，我们将探讨当冲突不可避免地发生时，如何有效地处理它们。这将主要介绍两大类策略：

• 开放定址法：当发生冲突时，通过特定的探测序列（如线性探测、二次探测）在散列表中寻找下一个空槽位置。
• 链地址法：将所有散列地址相同的记录链接在同一个链表中，散列表中存储链表的头指针。

掌握这些冲突处理机制，是构建一个健壮、高效哈希表的关键一步。 希望这篇总结能帮助你巩固对散列函数构造方法的理解。如果对某个具体方法有更深入的疑问，我们可以继续讨论。 互动与分享

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

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