考研笔记

散列查找及性能分析

这一节是第 7 章计算题的终点站。 教材的措辞是：「读者应能在给出散列表的长度、元素个数及散列函数和解决冲突的方法后，在求出散列表的基础上计算出查找成功时的平均查找长度和查找不成功的平均查找长度。」

难点只有一个：两个 的分母不一样，而且不成功那一个的分母不是表长。

机制

查找过程

散列表的查找过程与构造散列表的过程基本一致。对于一个给定的关键字 key，根据散列函数可以计算出其散列地址，执行步骤如下：

初始化：Addr = Hash(key)；

  1. 检测查找表中地址为 Addr 的位置上是否有记录：
    • 若无记录，返回查找失败；
    • 若有记录，比较它与 key 的值，若相等则返回查找成功标志，否则执行步骤 ②。
  2. 用给定的处理冲突方法计算「下一个散列地址」，并把 Addr 置为此地址，转入步骤 ①。

边界辨析：

「位置为空」才是失败的判据，不是「探遍全表」。 只要撞上一个空位就立刻返回失败—— 因为若该关键字存在，它在插入时就会占住这个空位。 这也正是 7.5.3 里「开放定址法不能物理删除」的原因： 物理删除会凭空造出一个空位，把后面同义词的查找路径截断。

完整例子：线性探测

关键字序列 ，散列函数 ，表长 ，用线性探测处理冲突，得到散列表 （教材图 7.34）：

地址0123456789101112131415
关键字140168275519208479231110

查找给定值 84：首先求得散列地址 ，因 L[6] 不空且 L[6]≠84，则找第一次冲突处理后的地址 ，而 L[7] 不空且 L[7]≠84，则找第二次冲突处理后的地址 ，L[8]=84，查找成功，返回记录在表中的序号 8。比较 3 次。

查找给定值 38：先求散列地址 ，L[12] 不空且 L[12]≠38，则找下一地址 ，因为 L[13] 是空记录，所以表中不存在关键字为 38 的记录。比较 2 次。

各关键字的比较次数（教材图 7.35）：

关键字140168275519208479231110
比较次数121431139113
成功

79 那个 9 值得看一眼：，而 全被占了，一路探测到 9 才落位。这就是堆积的代价——79 与 14、01 是同义词，但把它挡住的 68、27、55、19、20、84 里有一半根本不是它的同义词。

对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同。

不成功的 ：分母是值域大小

不成功 要对散列函数可能产生的每一个地址求平均，即分母是 （值域大小），不是表长 ，也不是记录数 。

理由从 7.5.2 的第 1 条要求直接来：散列函数的值域范围依赖于散列表的大小，而一个待查关键字的起点只可能落在值域内的某个地址上。地址 13、14、15 永远不会是任何 的取值，所以它们不作为起点参与平均。

对上例（，起点为 ），从每个起点沿线性探测走到第一个空位，空位本身也算一次比较：

起点0123456789101112
比较次数11312111098765432
不成功

注意起点 1 走了 13 次：从地址 1 一路撞到地址 12 全非空，直到地址 13 才空——这一个数字就把「线性探测的堆积有多贵」说清楚了。成功 而 不成功，差了近三倍。

关联对照：

「不成功比成功贵得多」这件事在本章反复出现。 顺序查找 成功 、不成功 ；折半查找 的两个 也不同； 散列表这里差距最大。 凡是题目只问「平均查找长度」而没说哪一个，先确认它问的是不是成功。

装填因子

表中记录数散列表长度

散列表的平均查找长度依赖于散列表的装填因子 ，而不直接依赖于 或 。 直观地看， 越大，表示装填的记录越「满」，发生冲突的可能性越大；反之发生冲突的可能性越小。

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

边界辨析：

「不直接依赖于 或 」是这一条的重点。 一张 的表和一张 的表， 都是 0.5，平均查找长度是同一个量级——表变大十倍，查找并不变慢。 这正是散列表被说成 的根据：代价只与「满的程度」有关，与「规模」无关。 与之对照，折半查找 的 是 ，直接依赖 。

教材 7.5.5 的题目里给过线性探测的一个近似式（作为题干条件给出，不是要求推导的结论）：

成功

手算模板

第一步：把表填出来（7.5.3 的模板），边填边记每个关键字的比较次数。

第二步：成功

成功每个关键字的比较次数记录数

第三步：不成功

  1. 起点范围是 （散列函数的值域），不是 。
  2. 对每个起点，沿冲突处理方法走，数到第一个空位为止，空位算一次。
  3. 除以 。

拉链法的两个 ：

数什么分母
成功每个结点在其链中的序号记录数
不成功每条链的长度（走到链尾的空指针；空链算 0 或 1 按题目约定）值域大小

三个分母，一个都不能混：成功除 ，不成功除 ，装填因子除 。

边界

说法判断说明
「不成功 的分母是表长 」❌是散列函数的值域大小
「不成功 的分母是 」❌同上； 是成功的分母
「查找失败要探遍全表」❌撞到第一个空位就失败
「空位不计入比较次数」❌计入——「检测该位置是否有记录」本身就是一次访问
「装填因子 」❌，分母是表长
「 依赖于表中记录数 」❌依赖于 ，不直接依赖 或
「 就不会冲突」❌冲突与 无必然关系， 只影响概率
「散列表查找成功的 ASL 仅与表长有关」❌取决于散列函数、处理冲突的方法和装填因子三者
「同一组关键字、同一散列函数，ASL 唯一」❌不同的冲突处理方法得到不同的表和不同的 ASL
「散列查找不需要比较关键字」❌定位后必须比较，所以仍以 ASL 度量效率

口径差异：

算竞里评价哈希表只看「均摊 」和「会不会被卡」，从不算 。 408 恰恰只考 ，而且两个 的分母是全章最容易错的地方—— 三个不同的分母（、、）在同一道题里同时登场。 这一节没有任何算法思想，纯粹是「按定义数数」，失分全在读题不细。

对照速查

量式子分母
成功各关键字比较次数记录数
不成功各起点探测到空位的次数值域大小
装填因子表长
线性探测近似—
教材例题（）值
成功2.5
不成功7
方法成功数什么不成功数什么
开放定址从 到落位的探测次数从起点到第一个空位的次数
拉链法结点在链中的序号链的长度

考点

  • 两个 的分母—— 与 ，全章最高频失分点。
  • 查找失败的判据是「遇到空位」，且空位计一次比较。
  • 装填因子 ，且 只依赖 （2011、2022 命题追踪）。
  • 影响查找效率的三个因素。
  • 同一组关键字、不同冲突处理方法 → 不同的表和不同的 ASL。
  • 完整填表 + 算两个 ASL（2010、2018、2019、2024 命题追踪，几乎年年考）。

链接

反向链接