考研笔记

散列表的基本概念与散列函数

散列表是本章唯一一种「不靠比较来定位」的查找结构。

前面所有方法——顺序、折半、二叉排序树、B 树——教材的原话是：记录在表中的位置与记录的关键字之间不存在映射关系，因此在这些表中的查找效率取决于比较的次数。 散列表反过来：建立了关键字和存储地址之间的一种直接映射关系，理想情况下查找的时间复杂度是 ，与表中元素的个数无关。

代价是「映射」不可能一一对应，于是有了冲突。这一章 7.5 的四个小节其实就是四个问题：怎么映射（7.5.2）、撞了怎么办（7.5.3）、撞完之后到底多快（7.5.4）。

机制

三个定义

术语定义
散列函数（哈希函数）一个把查找表中的关键字映射成该关键字对应的地址的函数，记为 。这里的地址可以是数组下标、索引或内存地址等
冲突 / 同义词散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生冲突的不同关键字称为同义词
散列表（哈希表）根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的一种直接映射关系

教材对冲突的态度写得很清楚，两句话是一对：

一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，因为这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

边界辨析：

「同义词」指的是关键字，不是地址。 两个关键字算不算同义词，只看 是否相等， 与用什么方法处理冲突、最终存到哪个位置无关。 用 线性探测 把同义词挪到别处之后，它们仍然是同义词； 而两个非同义词被挤到相邻位置引起的堆积，不叫同义词冲突——2014 年就考过这个区分。

构造散列函数的三条要求

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

第 1 条的后半句是 7.5.4 算 不成功 时的分母来源——查找失败的起点只可能是散列函数的一个取值，所以分母是值域大小而不是表长。这一点在 7.5.4 会用到。

四种散列函数

1. 直接定址法

直接取关键字的某个线性函数值为散列地址：

或

式中 和 是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况；若关键字分布不连续、空位较多，则会造成存储空间的浪费。

2. 除留余数法

这是一种最简单、最常用的方法。假定散列表表长为 ，取一个不大于 但最接近或等于 的质数 ：

除留余数法的关键是选好 ，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址，从而尽可能减少冲突的可能性。

3. 数字分析法

设关键字是 进制数（如十进制数），而 个数码在各位上出现的频率不一定相同。此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

4. 平方取中法

取关键字的平方值的中间几位作为散列地址。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好。在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况。

边界辨析：

和 是两个数，不要混。 是散列表的表长（数组开多大）， 是除留余数法里的模数（不大于 的最接近的质数）。 教材 7.5.4 的例子里 而 ——散列函数用 ， 而 开放定址 探测下一个地址时用的是 。 两个模数在同一道题里同时出现，是散列表计算题最集中的失分点。

手算模板

给定关键字序列建散列表：

  1. 抄下 （表长）和散列函数（多半是 ）。先把 和 分别圈出来。
  2. 按给定的插入顺序逐个算 。
  3. 位置空 → 放进去，比较次数记 1。
  4. 位置非空 → 按 7.5.3 的方法探测，每探测一次比较次数 +1。
  5. 边放边在旁边记下每个关键字的比较次数——这张表直接就是 成功 的分子。

边界

说法判断说明
「散列查找不需要任何关键字的比较」❌定位到地址后仍要比较该位置的关键字与 key 是否相等
「散列表的查找一定是 」⚠️理想情况下是；有冲突时取决于装填因子和处理冲突的方法
「同义词是指存储位置相同的关键字」❌是散列函数值相同的关键字，与最终存放位置无关
「装填因子 就能避免冲突」❌冲突取决于散列函数把哪些 key 映到同一地址，与表满不满无关
「直接定址法会产生冲突」❌不会产生冲突，但可能浪费空间
「除留余数法的 取表长 即可」❌取不大于 但最接近或等于 的质数
「 就是表长」❌；两者可以不等，且常常不等
「数字分析法适用于任何关键字集合」❌适用于已知的关键字集合；换了关键字要重构
「平方取中法只与关键字的中间几位有关」❌平方之后的中间几位与关键字的每一位都有关系
「散列函数越复杂越好」❌第 3 条要求是尽量简单

口径差异：

算法竞赛里写哈希是为了抗卡：随机化模数、双哈希、unordered_map 换 gp_hash_table， 关心的是最坏情况会不会被构造数据打爆。 408 完全不考这些，考的是「给定 和冲突处理方法，把表填出来、把两个 算出来」。 另外，「哈希」这个音译词在 408 里一律写成「散列」， 「散列表」「散列函数」「散列地址」是标准术语，答题时按教材用词更稳。

对照速查

散列函数公式特点适用
直接定址法 或 绝不冲突，可能浪费空间关键字分布基本连续
除留余数法最简单最常用，关键在选 通用； 取 的最接近质数
数字分析法取分布均匀的若干位依赖关键字集合关键字集合已知且各位分布不均
平方取中法取 的中间几位与每一位都有关各位取值都不够均匀
符号含义
散列表表长
除留余数法的模数， 且为质数
表中记录数
装填因子（见 7.5.4）

考点

  • 散列表 / 散列函数 / 冲突 / 同义词四个定义的准确措辞。
  • 同义词看的是 相等，不是存储位置相等。
  • 构造散列函数的三条要求，尤其「值域依赖表大小」。
  • 四种散列函数的适用场合，直接定址法不产生冲突。
  • 除留余数法的 是不大于 的最接近质数。
  • 与 的区分——散列用 ，探测用 。

链接

反向链接