哈希表长度为 11，哈希函数 H(k)=k mod 11，采用线性探测法处理冲突。按顺序插入关键字 19、14、23、1、68、20。在等概率成功查找的情况下，平均查找长度 ASL 为（）。
各关键字的成功查找比较次数分别为：19→1 次，14→1 次，23→1 次，1→2 次，68→3 次，20→1 次。总比较次数为 1+1+1+2+3+1=9，因此 ASL成功=9÷6=3/2。
选项分析
错误。只有完全没有冲突时，每个关键字成功查找才都只比较 1 次；本题关键字 1 和 68 发生了冲突。
错误。该结果通常来自漏算 68 探测槽 2 或槽 3 的一次比较，实际 68 要比较 3 次。
正确。六个关键字的成功比较次数合计 9 次，9÷6=3/2。
错误。不能把最大探测次数或冲突关键字数量直接当成平均查找长度。
本题为什么容易错
同学们常把“冲突次数”和“比较次数”混成一件事。68 在前两个槽位发生两次冲突，但成功查到槽 4 时还要再比较一次，所以它的成功查找长度是 3，不是 2。
简短答案
线性探测哈希表的成功平均查找长度 ASL 怎么算，正确答案是 C（3/2）。各关键字的成功查找比较次数分别为：19→1 次，14→1 次，23→1 次，1→2 次，68→3 次，20→1 次。总比较次数为 1+1+1+2+3+1=9，因此 ASL成功=9÷6=3/2。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 1 | 本题干扰项 | 错误。只有完全没有冲突时，每个关键字成功查找才都只比较 1 次；本题关键字 1 和 68 发生了冲突。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 4/3 | 本题干扰项 | 错误。该结果通常来自漏算 68 探测槽 2 或槽 3 的一次比较，实际 68 要比较 3 次。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 3/2 | 本题正确答案 | 正确。六个关键字的成功比较次数合计 9 次，9÷6=3/2。 | 看到题干核心场景时优先联想到它 |
| 2 | 本题干扰项 | 错误。不能把最大探测次数或冲突关键字数量直接当成平均查找长度。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 1：错误。只有完全没有冲突时，每个关键字成功查找才都只比较 1 次；本题关键字 1 和 68 发生了冲突。
- 4/3：错误。该结果通常来自漏算 68 探测槽 2 或槽 3 的一次比较，实际 68 要比较 3 次。
- 2：错误。不能把最大探测次数或冲突关键字数量直接当成平均查找长度。
知识点详解
哈希查找的比较次数取决于哈希函数、关键字插入顺序、冲突处理方法和装入因子。成功查找某关键字时，要从它的初始哈希地址开始，按插入时相同的探测规则检查，直到找到该关键字。成功 ASL 是各关键字成功比较次数的加权平均；题目没有给出访问概率时，通常按等概率处理。失败 ASL 的终止条件是遇到第一个空槽，并且通常要从每一个可能的初始地址分别统计，不能沿用成功 ASL 的分母。
备考速记
冲突两次不等于查找两次，最后找到自己的那一次也要算。
散列冲突在散列冲突场景中的作用
散列冲突在本题中的核心价值，是解决“哈希表长度为 11，哈希函数 H(k)=k mod 11，采用线性探测法处理冲突。按顺序插入关键字 19、14、23、1、68、20。在等概率成功查找的情况下，平均查找长度 ASL 为（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。
同类题怎么考
- 给出插入顺序和冲突处理方法，计算成功 ASL。
- 对所有可能的初始哈希地址统计失败 ASL。
- 比较线性探测、二次探测和链地址法对聚集现象的影响。
散列冲突在软件设计师软考中的考法
软考选择题通常不会只考概念定义，还会把散列冲突放到散列冲突场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。
解题思路
别急着套平均公式，先把 0 到 10 的槽位画出来。19 放在 8，14 放在 3，23 放在 1；关键字 1 从槽 1 开始，碰到 23 后放到 2，所以成功找到它要比较 2 次。68 的哈希地址是 2，依次碰到槽 2 的 1、槽 3 的 14，最后在槽 4 找到，共 3 次。20 放在 9，只比较 1 次。最后把六个次数相加再除以 6。
考点定位
成功 ASL 要对每个已存关键字沿其哈希探测序列重新计数。比较次数从检查第一个槽位开始算，不能只统计发生了几次冲突。
易错提醒
- 先把所有关键字一次性按哈希地址摆放，没有遵守题目给出的插入顺序。
- 线性探测时遇到占用槽位后跳着找，而不是按下一个槽位连续检查。
- 把成功 ASL 与失败 ASL 混算；失败查找还要统计遇到空槽才停止，分母口径也不同。
备考提示
- 画表时在关键字旁边顺手标注比较次数，例如 68(3)，最后求平均时不容易漏。
- 做完后检查负载因子。本题装入 6 个关键字、表长 11，负载因子为 6/11；装得越满，线性探测越容易形成堆积。
你可能还想了解
- 哈希表成功 ASL 和失败 ASL 有什么区别？
- 线性探测的比较次数从哪一次开始计算？
- 哈希表装入因子为什么会影响查找效率？
- 链地址法怎样计算成功平均查找长度？
本文小结
按插入顺序建立哈希表后，六个关键字的成功比较次数为1、1、1、2、3、1，合计9次，因此成功ASL为9/6=3/2。计算时要把找到关键字本身的最后一次比较也计入。