扫码获取 VIP 码
添加管理员微信获取 VIP 码
在数据结构这一章里，有一类题目几乎每年软考都会出现，考的就是哈希表。不少考生把哈希表当成一个死记硬背的知识点，背了哈希函数、背了冲突处理方法，结果一到计算题、辨析题就丢分。究其原因，是没有真正理解哈希表为什么存在、冲突为什么必然发生、平均查找长度到底在算一件什么事。这篇文章把散列表的概念、哈希函数的构造、冲突处理的两大流派、装填因子与平均查找长度的底层逻辑，以及命题人的挖坑套路，从头到尾梳理一遍。读完这一篇，哈希表相关的选择题和计算题，大概率能稳稳拿下。
要理解哈希表，必须先理解它想解决的那个问题。在顺序存储的表里查找一个关键字，要么顺序扫描，要么对有序表做二分查找。顺序查找的平均比较次数与表长线性相关，二分查找虽然把复杂度降到了对数级，却要求表在查找前完成排序，而且插入和删除都会破坏有序性，代价不低。树形结构比如二叉查找树、平衡二叉树，把查找、插入、删除都做到了对数级，但树形结构的节点之间要维护指针关系，实现复杂，且查找路径仍然要经过若干次比较。
哈希表走的是另一条完全不同的路。它的核心思想是让存储位置与关键字之间建立一种直接的函数关系，也就是通过一个散列函数，把关键字直接换算成它在表中的存储地址。理想情况下，给定一个关键字，只需要做一次函数计算，就能一步定位到目标位置，查找时间复杂度接近常数级。这种由关键字直接确定地址的方式，就是散列表赖以存在的根本理由。
这里需要把几个标准术语讲清楚。散列函数，习惯写作 H(key)，是把关键字映射为存储地址的规则。散列地址，是散列函数计算出来的那个位置下标。散列表，是实际存放记录的连续存储空间，它的长度通常记为 m。冲突，也叫碰撞，是指两个不同的关键字经过散列函数计算后得到了同一个地址。同义词，专指散列地址相同的那一组关键字，它们彼此互为同义词。装填因子，记为 α，等于表中已经存入的记录数 n 除以表的长度 m。这几个术语是理解后文一切机制的基石，必须先在脑子里立住。
哈希函数是散列表的第一道关卡。它的好坏直接决定了冲突发生的频率。设计哈希函数要满足两个基本要求：一是计算要尽可能简单，因为哈希表追求的就是快；二是散列地址要尽可能均匀地分布在整个表空间里，避免大量关键字挤在少数几个位置上。教材里罗列的常用构造方法有六种，它们的适用场景各不相同。
直接定址法是最朴素的一种，取关键字的某个线性函数值作为散列地址，也就是 H(key) 等于 key 或者 key 加上一个常数。这种方法的优点是绝对不会产生冲突，因为不同的关键字必然对应不同的地址。它的缺点是太依赖关键字的分布，只有当关键字本身就连续或者分布集中时才能用，一旦关键字稀疏、跨度大，表空间就会被严重浪费。所以直接定址法只适合关键字集合已知且规模不大的场合。
数字分析法适用于关键字位数较多、且各位数字分布不均匀的场景。它先分析所有关键字中每一位数字的出现频率，挑选分布最均匀的若干位拼接起来作为散列地址。比如身份证号这类关键字，前几位是地区码，中间是出生年月，重复度很高，不适合直接参与地址计算，而末几位往往分布得比较散，更适合作为散列地址的来源。数字分析法的本质是从关键字里筛选出随机性最强的信息来充当地址。
平方取中法是先把关键字平方，然后取结果中间若干位作为散列地址。这样做的原因是，一个数平方之后，中间那些位通常会同时受到关键字各位数字的影响，随机性比关键字本身更好。这种方法的好处是不需要事先了解关键字的分布，普适性较强，缺点是乘法运算相对稍重。
除留余数法是最常用也最重要的一种，软考的哈希计算题几乎都以它为基础。它的形式是 H(key) 等于 key 对某个整数 p 取余。这里的关键在于 p 的取值。教材反复强调，p 应当取不大于表长的最大质数。为什么是质数而不是任意数？因为取模运算的结果本质上取决于关键字对 p 的余数分布，如果 p 是质数，关键字序列的余数会更均匀地铺满零到 p 减一的区间，冲突概率更低；反过来，如果 p 是合数，比如取十的倍数，那么所有以相同末几位结尾的关键字都会落到相同的余数上，冲突会集中爆发。这条"模数取质数"的经验，是命题人特别爱考的细节。
折叠法适合关键字位数较长的情况。它先把关键字分割成若干等长的段，然后把各段相加，必要时再对相加结果取模，得到的值作为散列地址。折叠法又分移位折叠和边界折叠两种，前者各段直接对齐相加，后者把相邻段首尾反转后再相加。它的好处是把关键字的各位信息都揉进了地址计算里，避免只依赖某几个位。随机数法则适用于关键字长度不等的情况，它取关键字的随机函数值作为散列地址，通常用某种伪随机数生成器来实现。这两种方法在软考里出现的频率不如除留余数法高，但作为构造方法的完整拼图，考生应当知道它们的存在和适用场景。
很多考生第一次接触哈希表时会有一个疑问：既然哈希表的核心价值是常数级查找，为什么还要费力气研究冲突处理？答案是，冲突在绝大多数情况下是不可避免的。这里有两个层面的道理。
第一层是鸽巢原理，也就是抽屉原理。散列表的长度 m 是有限的，而可能的关键字数量几乎总是远大于 m。当存入的记录数 n 超过表的容量时，必然至少有两个关键字被映射到同一个地址。即便 n 还没超过 m，由于哈希函数只是把关键字"尽可能均匀"地撒开，而不是保证一一对应，冲突依然会以一定概率出现。所以冲突不是哈希表的缺陷，而是它天然的伴生现象，研究哈希表就必须研究如何处理冲突。
第二层是生日悖论带给人的直觉修正。人们往往以为，只有当表快满了才会频繁冲突，实际上冲突概率的上升速度远超直觉。生日悖论说的是，一个房间里只要二十三个人，就有超过一半的概率出现两个人同一天生日，而一年有三百六十五天。把这个结论平移到哈希表上就意味着，即使装填因子看起来不高，冲突也已经相当常见。装填因子 α 等于 n 除以 m，它是衡量散列表"拥挤程度"的核心指标。α 越接近一，冲突越剧烈，查找效率下降得越明显。因此，性能优化的一条主线就是控制装填因子：要么把表开大，要么在装填因子超过某个阈值时对散列表进行扩容重建。
正因为冲突概率对装填因子如此敏感，工程实践里通常会给散列表设定一个装填因子的上限阈值，常见的是零点七五。一旦插入新记录后装填因子超过这个阈值，就对散列表进行扩容，把表长翻倍并重新计算所有记录的散列地址，这个过程叫再散列或者重哈希。扩容虽然一次性开销较大，但从长期平均来看，能把装填因子压回一个合理的区间，保证查找效率稳定在接近常数级的水平。
开放定址法，也叫开放寻址法，是冲突处理的第一大流派。它的基本思路是，当某个关键字算出的地址已经被占用时，就按照一套预设的探查序列，在散列表里向后逐个寻找下一个空位，把记录放进去。所有记录都直接存放在散列表本体之内，不借助任何额外的链式结构，所以叫"开放定址"。根据探查序列的不同，它又细分出线性探查、二次探查、双重散列和伪随机探查几种。
线性探查是最简单的一种。当 H(key) 位置被占，就依次试探 H(key) 加一、加二、加三，直到找到空位，或者绕回表头继续找。它的实现最容易，但有一个明显的缺点叫聚集，也叫堆积。所谓聚集，是指一旦某个地址附近连续被占用了若干位置，后续关键字落到这一段时，探查序列会顺着这段连续的占用区一路延伸，导致这段区域越挤越长，形成一种"越冲突越密集、越密集越冲突"的正反馈。聚集会让查找和插入的平均探查长度明显增加，是线性探查效率下降的根源。
线性探查还带来一个必须处理的问题，就是删除。在开放定址法里，不能简单地把要删除的记录位置清空。因为清空之后，原本顺着它往后探查才能找到的那些同义词，它们的查找链就会被切断，后续查找会误以为关键字不存在。正确的做法是给被删除的位置打上"已删除"的标记，探查序列遇到这个标记时继续往后走，而插入时则可以把新记录放进这个带标记的位置。这个删除标记的细节，是理解开放定址法完整性的关键一环。
二次探查是为了缓解线性探查的聚集问题而提出的。它的探查步长不再是固定的加一，而是按照平方序列展开，比如加一的平方、加负一的平方、加二的平方、
本篇完！