题目

现有长度为 5，初始为空的散列表 HT，散列表函数 H(k) = (k+4) % 5 用线性探查再散列法解决冲突。若将关键字序列 2022,12,25 依次插入 HT 中，然后删除关键字 25，则 HT 中查找失败的平均查找长度（ ）。

错因

A

把"查找失败 ASL"算成了"每个 hash 槽 1 次比较"的均值，即 。忘了线性探测在冲突或非空槽位还要继续往后探测——单个 hash 起点的失败比较次数普遍 > 1。

B

在 H=4 槽上犯了经典陷阱：把"已删除标记"误当成"空槽"。删除 25 后位置 4 是删除标记，线性探测在删除标记处仍要继续往后探（直到遇到从未占用过的真空槽），这里要继续到位置 0 才能终止，共 2 次比较。把它算成 1 次的话得 。这就是 B 的来源。

D

可能多算了一次或者把删除标记当成"还在表里的有效 key"——比如算 H=4 时探测路径变成 4(25)→0(空)=2 次，但又在 H=0 时多算了一遍位置 4 的占用，得到偏大的结果。本质是把删除标记的语义在不同槽上算混了。

总解析

第一步：模拟插入

• → 位置 1
• → 位置 1 冲突，线性探测到位置 2
• → 位置 4

第二步：删除 25

线性探测不能直接清空位置 4——否则会切断后续元素的探测链路；只能打删除标记。表的最终状态：

地址	0	1	2	3	4
Key	空	2022	12	空	25 (deleted)

第三步：核心规则

线性探测查找失败的终止条件是遇到从未被占用过的真空槽。已删除位置（带删除标记）不是真空——必须继续往后探。

第四步：枚举 5 个可能的 hash 起点

H 起点	探测路径（每格记 1 次比较，遇真空终止）	比较次数
0	0(空)	1
1	1(2022) → 2(12) → 3(空)	3
2	2(12) → 3(空)	2
3	3(空)	1
4	4(deleted) → 0(空)	2

最终答案是 C（1.8）。