408 高频考点精讲:散列表(Hash Table)¶
模块归属:数据结构 · 查找
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:6 次(2016~2025 年:2018#9、2019#8、2022#9、2023#9、2024#42 大题、2025#9)
- 历年总考查频次:9 次(含 2010#9、2011#9、2014#7 等)
- 出题形式:单项选择题为主,2024 年命制综合解答题(第 42 题,分值 10 分)
- 命题特点:
- 考频极高且近年持续升温,2022~2025 年连续 4 年考查,并已登上涨分大题(2024 年 10 分大题)。
- 命题点全景覆盖:装填因子(Load Factor)计算与物理意义、散列函数构造法则(除留余数法素数选取)、开放定址法探测序列(线性探测、二次探测/平方探测变体、双散列)、同义词冲突与非同义词聚集(Primary Clustering 一次聚集与 Secondary Clustering 二次聚集)、逻辑删除与墓碑标记(Tombstone Deletion)机制、成功与失败平均查找长度(ASL)的精确计算(特别是散列函数模数与物理表长不一致时的基准入口确定)。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
- - √ √ - - √ √ √ √
(#9) (#8) (#9) (#9) (#42大题) (#9)
二、 具体考察内容¶
1. 散列表基本概念与数学定义¶
- 字典问题与直接寻址表的局限:
在常规查找结构中,若直接使用关键字作为数组下标(直接寻址表,Direct-address Table),当关键字全域空间 \(U\)$ \text{极大而实际存储的元素集合} $\(K \subseteq U\)$ \text{规模较小时(即} $\(|K| \ll |U|\)),直接寻址表将消耗灾难性的存储空间,且大多数槽位处于空置闲置状态。 - 散列技术(Hashing):
通过确定性的映射函数——散列函数(Hash Function)\(H\)$ \text{,将庞大的关键字集合} $\(U\)$ \text{映射到一个规模有限的地址空间} $\(\{0, 1, \dots, m-1\}\) 中: $\(H: U \to \{0, 1, \dots, m-1\}\)$ 由该映射机制建立的查找表即为散列表(Hash Table)。 - 冲突(Collision)与同义词(Synonyms):
对于散列函数 \(H\)$ \text{与任意两个不相等的关键字} $\(k_1, k_2 \in U\)(\(k_1 \neq k_2\)),若出现: $\(H(k_1) = H(k_2)\)$ 则称该现象为冲突(Collision)。此时关键字 \(k_1\)$ \text{与} $\(k_2\) 互为该散列函数在该散列表中的同义词(Synonyms)。
根据鸽巢原理(Pigeonhole Principle),当全域关键字数量 \(|U| > m\) 时,冲突在数学上是绝对不可避免的。散列表设计的核心研究课题便是如何有效降低冲突概率,并在发生冲突后高效化解冲突。 - 装填因子(Load Factor):
设散列表中实际存储的记录数量为 \(n\)$ \text{,散列表的物理空间容量(槽位总数/表长)为} $\(m\)$ \text{,则定义装填因子} $\(\alpha\) 为: $\(\alpha = \frac{n}{m}\)$ 装填因子 \(\alpha\)$ \text{标志着散列表的空间饱和程度。在开放定址法中,由于每个物理槽位至多存放一个元素,恒有} $\(\alpha < 1\)$ \text{;在拉链法中,每个槽位对应一个单链表,} $\(\alpha\) 可以大于或等于 1。
2. 常见散列函数构造方法及原理¶
散列函数设计的核心准则是:计算简捷快速且映射地址分布均匀,以最小化同义词冲突。
- 除留余数法(Division Method):
- 函数形式: $\(H(key) = key \bmod p\)$
- 参数选取约束:设散列表物理长度为 \(m\)$ \text{,除数} $\(p \le m\)$ \text{。为使关键字在表长} $\(m\)$ \text{的空间内最大程度分散,} $\(p\)$ \text{通常取不大于表长} $\(m\)$ \text{且最接近或等于} $\(m\) 的质数(素数)。
-
数论机理:若除数 \(p\)$ \text{含有较多约数(例如选为合数或 2 的整数次幂} $\(2^r\)$ \text{),则} $\(key \bmod 2^r\)$ \text{仅取决于} $\(key\)$ \text{的二进制最低} $\(r\) 位,高位信息完全被抹除,极易导致输入数据中的周期性模式转变为大量碰撞。选取质数能有效打乱输入关键字的代数公差与位模式,显著增强散列值的均匀性。
-
直接定址法(Direct Addressing):
- 函数形式:\(H(key) = a \cdot key + b\)(\(a, b\) 为常数)。
- 特征:属于单射线性映射,地址空间与关键字一一对应,理论上绝无冲突产生。
-
适用场景:关键字集合较小且连续分布的情况(如按年份统计人口年龄)。
-
数字分析法(Digital Analysis):
- 原理:针对已知结构的关键字全集,统计分析每一位数字的频数分布方差。剔除在各位上分布严重不均的数位,抽取离散分布较均匀的若干数位拼装作为散列地址。
-
适用场景:关键字位数较长且提前获知整体特征的场景(如手机号码、身份证号码)。
-
平方取中法(Mid-Square Method):
- 原理:首先求关键字的自乘平方值 \(key^2\),然后截取其运算结果中间的若干位二进制位或十进制位作为散列地址。
-
数论机理:平方运算能使关键字中的每一位数字都充分参与到乘法进位中,从而使乘积的中间数位受原数字全体各位的共同影响,增强随机离散度。
-
折叠法(Folding Method):
- 原理:将关键字从左至右分割成位数相等的若干段(最后一段可稍短),将各段按位相加并舍弃最高进位得到散列地址。分为移位折叠与分界折叠(交替折叠反转相加)。
3. 冲突解决策略深度剖析¶
(1)开放定址法(Open Addressing)¶
开放定址法的核心特征在于:所有元素均直接存放在散列表数组之内,不借用外部指针链表。当计算出的散列地址发生冲突时,通过系统化的探测序列规则在散列表中探测寻找下一个空闲槽位。
其通用的探测地址生成公式为:
$\(H_i(key) = (H(key) + d_i) \bmod m, \quad i = 1, 2, \dots, k \; (k \le m-1)\)$
根据增量序列 \(d_i\) 规则的不同,开放定址法细分为以下四类:
① 线性探测法(Linear Probing)¶
- 增量序列: $\(d_i = 1, 2, 3, \dots, m-1\)$
- 探测机制:依次顺序探测紧邻的下一个物理槽位:\((H_0 + 1) \bmod m, \; (H_0 + 2) \bmod m, \dots\)
- 全表遍历性定理:由于增量步长为 1,满足 \(\gcd(1, m) = 1\)$ \text{。根据初等数论,探测序列在} $\(i \in [0, m-1]\)$ \text{上构成了模} $\(m\)$ \text{的完全剩余系。因此,只要散列表中至少存在一个空闲槽位(即表未满,} $\(\alpha < 1\)$ \text{),线性探测序列必能覆盖表中所有} $\(m\) 个物理槽位,一定能够找到空闲位置(2025 年真题第 9 题 A 项考点)。
- 缺陷机理:极易产生一次聚集(Primary Clustering,又称堆积)。
② 二次探测法 / 平方探测法(Quadratic Probing)¶
- 标准增量序列: $\(d_i = 1^2, -1^2, 2^2, -2^2, \dots, k^2, -k^2 \quad (k \le \lfloor m/2 \rfloor)\)$
- 变体增量序列(如 2024 年真题):只取单侧正平方序列 \(d_i = 1^2, 2^2, 3^2, \dots, k^2\)。
- 遍历性限制与数论定理:
- 定理(二次剩余覆盖):二次探测无法遍历散列表的所有物理槽位。即便散列表尚未填满,二次探测序列也可能在部分槽位中循环,无法访问到未被探测覆盖的空闲槽位(2025 年真题第 9 题 B 项考点)。
- 特殊保证条件:当且仅当散列表表长 \(m\)$ \text{选取为满足} $\(m = 4k + 3\)$ \text{形式的素数时,采用交替正负二次探测序列,能够保证前} $\(m\)$ \text{次探测生成的地址互不相同,恰好能够探测到整个散列表中的} $\(\frac{m+1}{2}\) 个不同槽位(刚好覆盖超过一半的空间)。
- 优缺点:跳跃式探测能有效消除连续占用产生的一次聚集;但同义词之间依然沿着完全相同的步长序列探测,存在二次聚集(Secondary Clustering)。
③ 伪随机探测法(Pseudo-random Probing)¶
- 增量序列:\(d_i\) 采用预先确定的伪随机数发生器生成的离散整数序列。
④ 双散列法(Double Hashing)¶
- 增量序列: $\(d_i = i \times H_2(key), \quad i = 1, 2, \dots, m-1\)$ 探测地址公式: $\(H_i(key) = (H_1(key) + i \cdot H_2(key)) \bmod m\)$
- 原理分析:双散列法采用两个独立的散列函数 \(H_1\)$ \text{与} $\(H_2\)。\(H_1\)$ \text{计算初始基准槽位,} $\(H_2(key)\)$ \text{决定探测的步长。由于步长与关键字} $\(key\)$ \text{本身强相关,即使两个关键字} $\(k_1, k_2\)$ \text{产生初始碰撞(} $\(H_1(k_1) = H_1(k_2)\)$ \text{),其步长} $\(H_2(k_1)\)$ \text{与} $\(H_2(k_2)\) 大概率不同,从而分散到不同的探测轨迹上。
- 关键约束:步长 \(H_2(key)\)$ \text{必须与表长} $\(m\)$ \text{互质(} $\(\gcd(H_2(key), m) = 1\)$ \text{),且} $\(H_2(key) \not\equiv 0 \pmod m\),以保证探测序列能遍历整个散列表。
- 优点:彻底消除了一次聚集与二次聚集,是开放定址法中性能最优异的策略之一。
(2)拉链法 / 链地址法(Separate Chaining)¶
- 结构模型:建立一个大小为 \(m\)$ \text{的指针数组(槽头数组),所有散列到相同地址} $\(H(key)\) 的同义词均以节点形式链接在同一个单链表中。
- 核心优势:
- 冲突局限在同义词单链表内部,完全不存在开放定址法中的跨槽位占位冲突与聚集现象。
- 装填因子 \(\alpha = n / m\) 允许大于 1。
- 节点物理动态分配,删除操作极为直接,仅需对单链表进行常规的链表节点删除(修改指针并释放内存),不需要墓碑标记。
- 空间与缓存代价: 链表节点需额外存储指针域(32 位系统占 4 字节,64 位系统占 8 字节),带来额外的内存空间开销;且链表节点在物理内存中随机分布,破坏了 CPU Cache 的局部性(Spatial Locality)。
4. 聚集现象机理与学术辨析¶
在开放定址法中,“冲突”与“聚集”是两个不同维度的概念:
| 现象类型 | 英文名称 | 发生范围 | 本质机理 | 产生的冲突类型 | 影响后果 | 解决方案 |
|---|---|---|---|---|---|---|
| 一次聚集 (堆积) | Primary Clustering | 连续物理区域 | 线性探测的步长恒定为 1,占用槽位趋于相连成连续区块;散列到该连续块内任意位置的元素都会不断顺延扩大该区块(滚雪球效应) | 同义词冲突 与 非同义词冲突 并存 | 查找与插入的比较次数呈平方级急剧上升 | 二次探测、双散列、拉链法 |
| 二次聚集 | Secondary Clustering | 相同初始散列地址的元素群 | 探测步长仅依赖于探测轮次 \(i\),而与关键字无关;所有初始地址相同的同义词共享同一条探测轨迹 | 同义词之间 的后续探测冲突 | 同义词查找探测链过长 | 双散列法(步长绑定具体 key) |
- 同义词冲突与非同义词冲突辨析(2025 年真题第 9 题 C/D 项核心):
- 同义词冲突:关键字 \(k_1 \neq k_2\)$ \text{,初始计算满足} $\(H(k_1) = H(k_2)\),在初始入口即发生的碰撞。
- 非同义词冲突:关键字 \(k_1\)$ \text{与} $\(k_2\)$ \text{本身} $\(H(k_1) \neq H(k_2)\)$ \text{,但因为} $\(k_1\)$ \text{在处理其先前的冲突时探测并“占据”了} $\(H(k_2)\)$ \text{的物理槽位,当随后插入或查找} $\(k_2\)$ \text{时,在} $\(H(k_2)\)$ \text{槽位遭遇} $\(k_1\) 的拦截。这种冲突由槽位争夺产生,发生在非同义词之间。
- 结论:线性探测与二次探测等开放定址法,其处理的冲突既可能发生在同义词之间,也必然会发生因占位引起的非同义词之间。
5. 墓碑标记(Tombstone)逻辑删除机制¶
在开放定址法中,元素的物理删除操作存在极其严苛的约束。
(1)为何严禁直接物理置空?¶
开放定址法中,查找操作以遇到真正的空单元(EMPTY)作为查找失败的终止条件。
若直接将某个已存元素槽位物理重置为空单元:
设元素 \(A\)$ \text{存放在槽位} $\(k\)$ \text{;元素} $\(B\)$ \text{与} $\(A\)$ \text{发生冲突,探测后存放在槽位} $\(k+1\)。
若此时直接物理清空槽位 \(k\)$ \text{(置为空),后续查找元素} $\(B\)$ \text{时:首先计算} $\(H(B) = k\)$ \text{,检查槽位} $\(k\)$ \text{,发现该槽位为空,算法会立即判定“散列表中不存在元素} $\(B\)$ \text{”并终止查找,导致元素} $\(B\) 被意外“断链屏蔽”。
(2)墓碑标记工作流程¶
为解决上述问题,开放定址法必须采用逻辑删除(墓碑标记,Tombstone / DELETED):
1. 删除操作:将待删除元素的槽位状态由 OCCUPIED(占用)修改为 DELETED(墓碑标记),不物理抹除或将槽位置空。
2. 查找操作:探测过程中遇到 DELETED 状态的槽位,绝对不能终止探测,必须视同该槽位已被占用,继续沿着探测序列向下遍历,直至找到目标关键字或遇到真正的 EMPTY 槽位才终止。
3. 插入操作:探测过程中遇到 DELETED 槽位,记录首个遭遇的 DELETED 槽位地址,继续向后探测确认表中无重复键;若确认无重复键,可将新元素填入记录的该 DELETED 槽位并将其状态重置为 OCCUPIED,实现空间复用。
4. 查找失败 ASL 计算准则(2023 年真题第 9 题核心):
在计算查找失败比较次数时,墓碑单元必须计入比较次数,探测只有在命中未曾使用过的纯净 EMPTY 单元时才真正停机。
5. 动态再散列(Rehashing):
过多的墓碑标记会导致查找失败甚至查找成功的探测路径冗长。当墓碑数量超过预设阈值或装填因子超出警戒线时,系统必须触发重新散列(Rehash),开辟新表并将现存有效元素重新计算散列值插入,彻底清除所有墓碑标记。
6. 平均查找长度(ASL)理论与计算体系¶
(1)影响 ASL 的三大核心要素(2022 年真题第 9 题)¶
散列查找的平均查找长度(Average Search Length, ASL)是衡量散列表性能的最核心指标,直接由以下三个因素共同决定: 1. 装填因子 \(\alpha\)$ \text{:表征散列表的饱满程度。} $\(\alpha\)$ \text{越大,表内空槽越稀疏,发生碰撞的概率呈非线性指数级增长,ASL 显著增大;反之} $\(\alpha\) 越小,冲突越少,但空间冗余度大。 2. 散列函数:决定关键字在整个槽位空间内的离散度与均匀度。散列函数若能近似满足均匀散列假设(Simple Uniform Hashing Assumption),同义词冲突即可最小化;若散列函数有偏,则引发大规模同义词冲突。 3. 冲突解决策略:决定发生初始冲突后的重定位轨迹。线性探测容易导致严重的一次聚集;二次探测与双散列显著离散了冲突路径;拉链法则将冲突严格隔离在各个独立的同义词链表中。不同策略在相同 \(\alpha\) 下的理论 ASL 公式存在本质差异。
(2)成功平均查找长度(ASL(succ))计算模型¶
查找成功指查找的关键字确已存在于散列表中,且每个已存关键字具有等概率访问前提: $\(\text{ASL}_{\text{succ}} = \frac{1}{n} \sum_{i=1}^n C_i\)$ 其中: - \(n\) 为散列表中实际存储的有效元素总数; - \(C_i\)$ \text{为定位到第} $\(i\) 个关键字所必须经历的关键字比较次数(即探测步数)。
(3)失败平均查找长度(ASL(unsucc))计算模型¶
查找失败指待查关键字并不在散列表中。
$\(\text{ASL}_{\text{unsucc}} = \frac{1}{r} \sum_{j=0}^{r-1} C_j\)$
其中:
- 分母 \(r\)(极易错点):是待查关键字经散列函数计算后可能落入的初始入口地址总数(即散列函数的值域基数)。
例如采用除留余数法 \(H(key) = key \bmod p\)$ \text{时,} $\(r = p\)$ \text{。严禁除以散列表的物理长度} $\(m\)$ \text{(2019 年真题第 8 题核心陷阱,表中} $\(p=7, m=11\),分母必须是 7)。
- 分子各项 \(C_j\)$ \text{:假设关键字的初始散列地址为} $\(j\)(\(0 \le j \le r-1\)$ \text{),从槽位} $\(j\) 出发沿探测序列向下比较,直到遇到第一个真正空单元(EMPTY)时所经历的关键字比较次数(探测到 EMPTY 单元本身也计为 1 次判断比较)。
(4)理论极限公式参考(均匀散列假设下)¶
| 冲突解决机制 | 查找成功理论期望 \(\text{ASL}_{\text{succ}}\)$ \text{ | 查找失败理论期望} $\(\text{ASL}_{\text{unsucc}}\) |
|---|---|---|
| 拉链法 | \(\approx 1 + \frac{\alpha}{2}\) | \(\approx \alpha\)$ \text{(若计入链尾 NULL 判空则为} $\(1+\alpha\)) |
| 开放定址法 · 线性探测 | \(\approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)\) | \(\approx \frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)\) |
| 开放定址法 · 理想双散列 | \(\approx \frac{1}{\alpha}\ln\frac{1}{1-\alpha}\) | \(\approx \frac{1}{1-\alpha}\) |
三、 近十年真题精讲(2016~2025)¶
近十年(2016~2025 年)408 统考真题中,散列表共考查 6 次,包含 5 道单项选择题与 1 道 10 分综合解答大题。
【真题 1】2025 年 408 第 9 题 · 冲突处理性质与同义词辨析¶
题目
下列关于散列法处理冲突的叙述中,正确的是( )。
A. 只要散列表不满,线性探查再散列一定能找到一个空闲位置
B. 只要散列表不满,二次探查再散列一定能找到一个空闲位置
C. 线性探查再散列处理的冲突,一定是发生在同义词之间
D. 二次探查再散列处理的冲突,一定是发生在非同义词之间
【解析】¶
-
A 项正确:
线性探测法的探测增量序列为 \(d_i = 1, 2, \dots, m-1\)$ \text{。其探测地址序列为} $\(H_i = (H_0 + i) \bmod m\)。
由于增量步长为 1,满足 \(\gcd(1, m) = 1\)$ \text{。根据初等数论中的完全剩余系性质,探测序列} $\((H_0 + i) \bmod m\)$ \text{在} $\(i \in [0, m-1]\)$ \text{上构成了模} $\(m\)$ \text{的完全剩余系,能够无遗漏地遍历散列表的全部} $\(m\) 个物理槽位。
因此,只要散列表中至少存在一个空位(即散列表未满),线性探测必然能够探测到该空闲位置。 -
B 项错误:
二次探测法(平方探测法)的标准增量序列为 \(d_i = 1^2, -1^2, 2^2, -2^2, \dots, k^2, -k^2\)。
受限于模 \(m\)$ \text{下二次剩余的分布规律,二次探测序列无法遍历全表。即便在最佳理论条件下(表长} $\(m\)$ \text{为形如} $\(4k+3\)$ \text{的素数),二次探测序列最多也只能探测到散列表中的} $\(\frac{m+1}{2}\) 个互不相同的物理槽位(仅占全表约一半)。
若散列表尚有空闲位置,但空闲位置恰好处于二次探测无法触及的剩余一半槽位中,二次探测便会陷入死循环而无法定位到该空闲位置。 -
C 项与 D 项错误:
在开放定址法(无论是线性探测还是二次探测)中: - 当两个不同的关键字 \(k_1\)$ \text{与} $\(k_2\)$ \text{满足} $\(H(k_1) = H(k_2)\)$ \text{时,它们会竞争同一初始地址} $\(H_0\),此为同义词冲突;
- 当元素 \(k_1\)$ \text{在发生同义词冲突后通过探测占据了位置} $\(p\)(\(p \neq H(k_1)\)$ \text{),后续新插入的元素} $\(k_3\)$ \text{若初始计算恰好} $\(H(k_3) = p\)$ \text{,则} $\(k_3\)$ \text{与} $\(k_1\)$ \text{并非同义词(} $\(H(k_1) \neq H(k_3)\)$ \text{),但} $\(k_3\)$ \text{在槽位} $\(p\)$ \text{依然会因} $\(k_1\) 的占位而发生碰撞。此为由堆积(聚集)现象引发的非同义词冲突。
因此,线性探查与二次探查所处理的冲突,均既可能发生在同义词之间,也可能发生在非同义词之间。
正确答案:A
【真题 2】2024 年 408 第 42 题 · 散列表构造与查找序列(综合解答题,10分)¶
题目
将关键字 20, 3, 11, 18, 9, 14, 7 依次存储到长度为 11 的散列表 HT 中,散列函数为 \(H(key) = (key \times 3) \bmod 11\)。\(H_0\)$ \text{为初始散列地址,} $\(H_1, H_2, H_3, \dots, H_k\)$ \text{分别为第 1 次冲突、第 2 次冲突、第 3 次冲突、} $\(\dots\)$ \text{、第} $\(k\)$ \text{次冲突时探测的地址。} $\(H_k = (H_0 + k^2) \bmod 11\)。
请回答下列问题:
(1) 画出所构造的 HT,并计算 HT 的装填因子(6分)
(2) 给出在 HT 中查找关键字 14 的关键字比较序列(2分)
(3) 在 HT 中查找关键字 8,确认查找失败时的散列地址是多少?(2分)
【解析】¶
(1) 散列表 HT 构造与装填因子计算¶
表长 \(m = 11\)$ \text{,合法下标索引范围为} $\(0 \sim 10\)。
散列函数:\(H(key) = (key \times 3) \bmod 11\)$ \text{;冲突探测公式:} $\(H_k = (H_0 + k^2) \bmod 11\)。
依次插入各关键字的精确推导过程如下:
- 插入 20:
\(H_0 = (20 \times 3) \bmod 11 = 60 \bmod 11 = 5\)。
HT[5] 为空,直接放入:HT[5] = 20。 - 插入 3:
\(H_0 = (3 \times 3) \bmod 11 = 9 \bmod 11 = 9\)。
HT[9] 为空,直接放入:HT[9] = 3。 - 插入 11:
\(H_0 = (11 \times 3) \bmod 11 = 33 \bmod 11 = 0\)。
HT[0] 为空,直接放入:HT[0] = 11。 - 插入 18:
\(H_0 = (18 \times 3) \bmod 11 = 54 \bmod 11 = 10\)。
HT[10] 为空,直接放入:HT[10] = 18。 - 插入 9:
\(H_0 = (9 \times 3) \bmod 11 = 27 \bmod 11 = 5\)。
HT[5] 已被 20 占用,发生第 1 次冲突!
执行二次探测:\(H_1 = (5 + 1^2) \bmod 11 = 6\)。
HT[6] 为空,存入:HT[6] = 9。 - 插入 14:
\(H_0 = (14 \times 3) \bmod 11 = 42 \bmod 11 = 9\)。
HT[9] 已被 3 占用,发生第 1 次冲突!
探测 \(H_1 = (9 + 1^2) \bmod 11 = 10\);HT[10] 已被 18 占用,发生第 2 次冲突!
探测 \(H_2 = (9 + 2^2) \bmod 11 = 13 \bmod 11 = 2\)。
HT[2] 为空,存入:HT[2] = 14。 - 插入 7:
\(H_0 = (7 \times 3) \bmod 11 = 21 \bmod 11 = 10\)。
HT[10] 已被 18 占用,发生第 1 次冲突!
探测 \(H_1 = (10 + 1^2) \bmod 11 = 11 \bmod 11 = 0\);HT[0] 已被 11 占用,发生第 2 次冲突!
探测 \(H_2 = (10 + 2^2) \bmod 11 = 14 \bmod 11 = 3\)。
HT[3] 为空,存入:HT[3] = 7。
构造完成后的散列表 HT 如下表所示:
| 地址索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 存储内容 | 11 | 空 | 14 | 7 | 空 | 20 | 9 | 空 | 空 | 3 | 18 |
装填因子计算:
表中关键字个数 \(n = 7\)$ \text{,散列表长度} $\(m = 11\),因此装填因子为:
$\(\alpha = \frac{n}{m} = \frac{7}{11} \approx 0.636\)$
(2) 查找关键字 14 的关键字比较序列¶
- 计算关键字 14 的初始散列地址:
\(H_0 = (14 \times 3) \bmod 11 = 42 \bmod 11 = 9\)。
访问 HT[9],读取关键字 3 进行比较:\(3 \neq 14\),比较不匹配; - 执行第 1 次探测:
\(H_1 = (9 + 1^2) \bmod 11 = 10\)。
访问 HT[10],读取关键字 18 进行比较:\(18 \neq 14\),比较不匹配; - 执行第 2 次探测:
\(H_2 = (9 + 2^2) \bmod 11 = 13 \bmod 11 = 2\)。
访问 HT[2],读取关键字 14 进行比较:\(14 = 14\),查找成功。
因此,查找关键字 14 的比较序列为:3 \(\to\) 18 \(\to\) 14(或写为3, 18, 14,共经历 3 次比较)。
(3) 查找关键字 8 确认失败时的散列地址¶
- 计算关键字 8 的初始散列地址:
\(H_0 = (8 \times 3) \bmod 11 = 24 \bmod 11 = 2\)。
检查 HT[2],存储内容为 14(\(14 \neq 8\)),继续探测; - 探测 \(H_1 = (2 + 1^2) \bmod 11 = 3\):
检查 HT[3],存储内容为 7(\(7 \neq 8\)),继续探测; - 探测 \(H_2 = (2 + 2^2) \bmod 11 = 6\):
检查 HT[6],存储内容为 9(\(9 \neq 8\)),继续探测; - 探测 \(H_3 = (2 + 3^2) \bmod 11 = 11 \bmod 11 = 0\):
检查 HT[0],存储内容为 11(\(11 \neq 8\)),继续探测; - 探测 \(H_4 = (2 + 4^2) \bmod 11 = 18 \bmod 11 = 7\):
检查 HT[7],发现 HT[7] 为空!
在开放定址法中,一旦探测到空闲单元,即证明该关键字绝对不可能在后续探测序列中,查找立即以失败停机。
因此,确认查找失败时的散列地址是 7。
【真题 3】2023 年 408 第 9 题 · 墓碑标记与查找失败 ASL 计算¶
题目
现有长度为 5,初始为空的散列表 HT,散列函数 \(H(k) = (k+4) \bmod 5\),用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入 HT 中,然后删除关键字 25,则 HT 中查找失败的平均查找长度( )。
A. 1 B. 1.6 C. 1.8 D. 2.2
【解析】¶
- 依次插入关键字(表长 \(m = 5\)$ \text{,地址范围} $\(0 \sim 4\)):
- 插入 2022:\(H(2022) = (2022 + 4) \bmod 5 = 2026 \bmod 5 = 1\)。HT[1] 为空,存入:
HT[1] = 2022。 - 插入 12:\(H(12) = (12 + 4) \bmod 5 = 16 \bmod 5 = 1\)$ \text{。HT[1] 冲突,线性探测} $\(H_1 = (1 + 1) \bmod 5 = 2\)。HT[2] 为空,存入:
HT[2] = 12。 -
插入 25:\(H(25) = (25 + 4) \bmod 5 = 29 \bmod 5 = 4\)。HT[4] 为空,存入:
HT[4] = 25。 -
删除关键字 25 与墓碑标记设置:
- 在开放定址法中,物理删除会导致探测链断裂。因此删除 HT[4] 中的 25 必须打上墓碑标记(DELETED),而非直接物理置空。
-
此时散列表的物理状态为:
- HT[0]:空(EMPTY)
- HT[1]:2022(OCCUPIED)
- HT[2]:12(OCCUPIED)
- HT[3]:空(EMPTY)
- HT[4]:DELETED(墓碑标记)
-
计算查找失败的平均查找长度: 散列函数为 \(H(k) = (k+4) \bmod 5\)$ \text{,其像集为模 5 的剩余类} $\(\{0, 1, 2, 3, 4\}\)$ \text{,故任意待查关键字的初始散列入口等概率落在} $\(0, 1, 2, 3, 4\)$ \text{这 5 个地址上(分母} $\(r = 5\))。
在查找过程中,遇到墓碑标记必须视同非空并继续向下探测,只有遭遇纯净空单元(EMPTY)才能断定查找失败: - 初始地址为 0:
首先访问 HT[0],HT[0] 为空单元,直接确认查找失败。比较次数 = 1。 - 初始地址为 1:
访问 HT[1](存有 2022),不匹配;
探测到 HT[2](存有 12),不匹配;
探测到 HT[3](空单元),确认查找失败。比较序列为 HT[1], HT[2], HT[3],比较次数 = 3。 - 初始地址为 2:
访问 HT[2](存有 12),不匹配;
探测到 HT[3](空单元),确认查找失败。比较序列为 HT[2], HT[3],比较次数 = 2。 - 初始地址为 3:
首先访问 HT[3],HT[3] 为空单元,直接确认查找失败。比较次数 = 1。 -
初始地址为 4:
访问 HT[4](墓碑标记 DELETED),不能判定为空,必须继续向下探测;
线性探测循环回到 \((4+1) \bmod 5 = 0\);
访问 HT[0](空单元),确认查找失败。比较序列为 HT[4], HT[0],比较次数 = 2。 -
求均值: $\(\text{ASL}_{\text{unsucc}} = \frac{1 + 3 + 2 + 1 + 2}{5} = \frac{9}{5} = 1.8\)$
正确答案:C
【真题 4】2022 年 408 第 9 题 · 影响散列查找 ASL 的三大要素¶
题目
下列因素中,影响散列(哈希)方法平均查找长度的是( )。
I. 装填因子 II. 散列函数 III. 冲突解决策略
A. 仅 I、II B. 仅 I、III C. 仅 II、III D. I、II、III
【解析】¶
散列查找的平均查找长度(ASL)取决于关键字在散列表中的冲突频率与冲突发生后的探测路径长度。题中三个因素均对其具有直接决定作用:
1. 因素 I(装填因子 \(\alpha = n / m\)):
装填因子反映散列表的拥挤程度。\(\alpha\) 越大,表内剩余可用空间越少,后续关键字插入时命中已被占用槽位的概率急剧增加,导致探测比较链显著拉长,ASL 显著变大。
2. 因素 II(散列函数):
散列函数的优劣决定了关键字在地址空间中的映射均匀程度。优良的散列函数能使关键字均匀分散在各个槽位,降低初始同义词冲突概率;不良的散列函数会导致大量关键字映射到同一局部槽位,造成局部冲突聚集,使 ASL 严重恶化。
3. 因素 III(冲突解决策略):
不同的冲突解决策略(如线性探测、二次探测、双散列、拉链法)决定了发生初始冲突后的重定位规则。例如线性探测容易引发一次聚集,导致 ASL 随装填因子上升而急速恶化;二次探测与双散列能有效化解一次聚集;拉链法则将同义词冲突控制在链表内部,不同策略下计算出的 ASL 理论值与实际值均截然不同。
综上所述,I、II、III 均是影响平均查找长度的核心决定因素。
正确答案:D
【真题 5】2019 年 408 第 8 题 · 线性探测查找失败 ASL 计算与基准入口陷阱¶
题目
现有长度为 11 且初始为空的散列表 HT,散列函数是 \(H(key) = key \bmod 7\),采用线性探查(线性探测再散列)法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20 依次插入到 HT 后,HT 查找失败的平均查找长度是( )。
A. 4 B. 5.25 C. 6 D. 6.29
【解析】¶
- 构造散列表 HT(表长 \(m = 11\)$ \text{,增量步长} $\(d_i = 1\)):
- 87: \(87 \bmod 7 = 3\) \(\to\) HT[3] = 87
- 40: \(40 \bmod 7 = 5\) \(\to\) HT[5] = 40
- 30: \(30 \bmod 7 = 2\) \(\to\) HT[2] = 30
- 6: \(6 \bmod 7 = 6\) \(\to\) HT[6] = 6
- 11: \(11 \bmod 7 = 4\) \(\to\) HT[4] = 11
- 22: \(22 \bmod 7 = 1\) \(\to\) HT[1] = 22
- 98: \(98 \bmod 7 = 0\) \(\to\) HT[0] = 98
- 20: \(20 \bmod 7 = 6\) \(\to\)$ \text{冲突!探测到 HT[7],HT[7] 为空} $\(\to\) HT[7] = 20
此时散列表 HT 的物理状态如下:
| 地址索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 98 | 22 | 30 | 87 | 11 | 40 | 6 | 20 | 空 | 空 | 空 |
-
核心陷阱剖析:查找失败的入口地址范围与分母确定:
散列函数是 \(H(key) = key \bmod 7\)$ \text{。对于任意输入的关键字} $\(key\)$ \text{,其初次散列计算出的目标地址只能是} $\(0 \sim 6\)$ \text{之间的整数,绝不可能直接散列到地址} $\(7 \sim 10\)。
因此,查找失败的可能入口只有 7 个(即 \(0, 1, 2, 3, 4, 5, 6\)),分母必须取 7,而非表长 11! -
统计各入口查找失败的比较次数(探测至首个空单元 HT[8]):
从当前入口开始向右线性探测,直到遇到第一个空单元 HT[8] 停止: - 入口为 0:检查 HT[0] 至 HT[8],共比较 \(8 - 0 + 1 =\) 9 次;
- 入口为 1:检查 HT[1] 至 HT[8],共比较 \(8 - 1 + 1 =\) 8 次;
- 入口为 2:检查 HT[2] 至 HT[8],共比较 \(8 - 2 + 1 =\) 7 次;
- 入口为 3:检查 HT[3] 至 HT[8],共比较 \(8 - 3 + 1 =\) 6 次;
- 入口为 4:检查 HT[4] 至 HT[8],共比较 \(8 - 4 + 1 =\) 5 次;
- 入口为 5:检查 HT[5] 至 HT[8],共比较 \(8 - 5 + 1 =\) 4 次;
-
入口为 6:检查 HT[6] 至 HT[8],共比较 \(8 - 6 + 1 =\) 3 次。
-
计算查找失败平均查找长度: $\(\text{ASL}_{\text{unsucc}} = \frac{9 + 8 + 7 + 6 + 5 + 4 + 3}{7} = \frac{42}{7} = 6\)$
正确答案:C
【真题 6】2018 年 408 第 9 题 · 线性探测查找成功 ASL 基础计算¶
题目
现有长度为 7、初始为空的散列表 HT,散列函数 \(H(k) = k \bmod 7\),用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到 HT 后,查找成功的平均查找长度是( )。
A. 1.5 B. 1.6 C. 2 D. 3
【解析】¶
- 依次插入关键字(表长 \(m = 7\)$ \text{,地址范围} $\(0 \sim 6\)):
- 插入 22:\(H(22) = 22 \bmod 7 = 1\)。HT[1] 为空,放入
HT[1] = 22。比较次数为 1。 - 插入 43:\(H(43) = 43 \bmod 7 = 1\)$ \text{。HT[1] 冲突,线性探测} $\(H_1 = (1 + 1) \bmod 7 = 2\)。HT[2] 为空,放入
HT[2] = 43。比较次数为 2。 -
插入 15:\(H(15) = 15 \bmod 7 = 1\)$ \text{。HT[1] 冲突;探测} $\(H_1 = 2\)$ \text{(存有 43)仍冲突;探测} $\(H_2 = (1 + 2) \bmod 7 = 3\)。HT[3] 为空,放入
HT[3] = 15。比较次数为 3。 -
计算查找成功的平均查找长度:
散列表中共有 \(n = 3\) 个元素,每个元素被等概率访问: $\(\text{ASL}_{\text{succ}} = \frac{1 + 2 + 3}{3} = \frac{6}{3} = 2\)$
正确答案:C
四、 核心解题套路与易错陷阱¶
1. 散列表题型通用解题三步法(草稿纸表格化流)¶
无论是选择题还是综合大题,在草稿纸上规范列出两行三列的辅助追踪表,是杜绝计算失误的核心解题范式:
- 第一步:标定物理表长与散列入口范围:
- 明确物理表长 \(m\)$ \text{(决定下标从} $\(0\)$ \text{到} $\(m-1\));
- 明确模数 \(p\)$ \text{(决定散列函数} $\(H(key)\)$ \text{的初次落点范围为} $\(0 \sim p-1\))。
- 第二步:按序模拟入表,记录单元素比较成本:
严格按照给定的冲突公式(线性递增、平方正负交替或单侧平方)在草稿纸上推进。每发生一次占用碰撞,比较次数加 1。 - 第三步:分流计算 ASL:
- 求 \(\text{ASL}_{\text{succ}}\)$ \text{:求和表中各元素的比较次数,除以元素总数} $\(n\);
- 求 \(\text{ASL}_{\text{unsucc}}\)$ \text{:只针对} $\(0 \sim p-1\)$ \text{的每个合法入口,分别计数其向后探测直至首个纯净空槽(EMPTY)所跨越的槽位数(含该空槽),求和后除以入口数} $\(p\)。
2. 四大命题陷阱深度警示¶
陷阱一:查找失败时分母盲目除以表长 m¶
- 错误直觉:认为散列表长度为 \(m\)$ \text{,查找失败自然应该除以} $\(m\)。
- 真题对照:2019 年真题第 8 题中,表长 \(m = 11\)$ \text{,散列函数为} $\(key \bmod 7\)。
- 防坑准则:散列查找的第一步必然是执行散列函数计算。若散列函数为 \(key \bmod 7\)$ \text{,则任何合法的关键字绝不可能散列生成地址} $\(7, 8, 9, 10\)$ \text{。因此查找失败时可能的初始探索入口只有} $\(0 \sim 6\)$ \text{共 7 种等可能情况,分母必须是除数} $\(p\)(即 7),除以 11 属于原则性概念错误。
陷阱二:忽略墓碑标记,将逻辑删除视为空单元终止探测¶
- 错误直觉:看到表中标记为
DELETED,便认为此处“没有元素”,查找至此时即判定查找失败停机。 - 真题对照:2023 年真题第 9 题。
- 防坑准则:墓碑标记(Tombstone)是维系开放定址法探测链连续性的必要机制。遇到墓碑必须视同占用并继续向后探测。在计算查找失败比较次数时,墓碑单元必须计入探测比较次数,唯有遭遇从未被占用的真正空单元(EMPTY)方可判定失败。
陷阱三:混淆二次探测增量序列的正负号交替次序¶
- 错误直觉:误将增量记为 \(1^2, 2^2, 3^2, 4^2\)(单侧),或在正负交替时算错模运算负数映射。
- 防坑准则:
- 若考题未明确声明,标准二次探测增量严格为正负交替:\(+1^2, -1^2, +2^2, -2^2, \dots\);
- 若考题给出了具体公式(如 2024 年第 42 题明确定义 \(H_k = (H_0 + k^2) \bmod 11\)),必须严格遵照题设公式计算,切忌套用常规记忆;
- 在遇到负数求模时,需遵循数学规范:例如在模 11 下,\((-1) \bmod 11 = 10\),\((-4) \bmod 11 = 7\)。
陷阱四:同义词与非同义词概念混淆¶
- 错误直觉:认为只要在探测中撞上了已存元素,两者就是“同义词”。
- 真题对照:2025 年真题第 9 题。
- 防坑准则:
- 同义词:当且仅当 \(H(k_1) = H(k_2)\),源于散列函数本身的映射重叠;
- 非同义词:\(H(k_1) \neq H(k_2)\),其碰撞源于开放定址法中元素因冲突外溢而挤占了其他散列地址(一次聚集/堆积)。
五、 考点速记清单¶
- 散列函数核心:除留余数法中,\(p\)$ \text{取小于或等于表长} $\(m\) 的最大质数。
- 装填因子公式:\(\alpha = n / m\)$ \text{(元素数除以物理槽位数)。} $\(\alpha\) 越大,冲突率越高,ASL 呈非线性急剧上升。
- 线性探测遍历性:只要散列表未满,步长 1 保证遍历模 \(m\) 完全剩余系,必然能找到空位;但易引发一次聚集(堆积)。
- 二次探测局限性:无法探测全表,即使未满也可能找不到空位;可消除一次聚集,但存在二次聚集。
- 双散列优势:第二散列函数 \(H_2(key)\) 决定探测步长,探测轨迹与关键字本身绑定,彻底消除一次聚集与二次聚集。
- 墓碑删除机制:开放定址法删除必须打上墓碑标记(
DELETED)。查找遇到墓碑继续探测,遇到真正空单元才失败。 - ASL 成功速算:分母是实际插入元素个数 \(n\),分子是各元素查找到时所需比较次数之和。
- ASL 失败速算:分母是散列函数的值域基数 \(p\)$ \text{(非表长} $\(m\)$ \text{!),分子是从各入口} $\(0 \sim p-1\) 出发探测到首个真正空单元的步数之和。