题目

现有长度为 7、初始为空的散列表 HT，散列函数 H(k) = k % 7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插人到 HT 后，查找成功的平均查找长度是( )

错因

A

只算了前两个关键字。22 比较 1 次、43 比较 2 次、15 漏算 → 。本质上是把"等到所有元素都插入完之后再统一算 ASL"理解成了"每插一个就算一次再求平均"，结果丢掉了 15 那一项。

B

把分母错写成 5（或其它数字）凑出 1.6。一个常见走法：在统计每个关键字"探测过的下标个数"时，把空槽也勉强算了进去 也不对，但和"加权平均"混杂运算可能凑得 1.6。本质都是平均时分子或分母数错了——ASL_succ 的标准做法是"每个已插入关键字查找成功一次需要的比较次数之和 ÷ 已插入关键字个数"，分母只能是 3。

D

把"查找成功最多比较多少次"当成了"平均比较多少次"。15 这个关键字的确需要比较 3 次才命中，但平均不是最大值。选 D 的人通常没意识到平均查找长度是算术平均而不是"取最坏情况"。

总解析

线性探测的插入流程：哈希到 位置；若该位置已占，则探测 （mod 表长）直到遇到空槽。插入时探测了多少个位置（含命中的那一个），将来查找成功时也要比较多少次——因为查找走的是同一条探测链。

逐个插入（表长 ，）：

关键字		探测过程	落点下标	查找成功比较次数
22		HT[1] 空，直接放	1	1
43		HT[1] 已占（22）→ 探 HT[2] 空，放	2	2
15		HT[1] 占 → HT[2] 占 → HT[3] 空，放	3	3

得到散列表（下标 0–6）：

下标	0	1	2	3	4	5	6
内容	空	22	43	15	空	空	空

计算 ASL（成功）：

直观上，三个元素全部哈希到同一个槽 1，被线性探测连续推到 1、2、3 三个位置，分别需要 1、2、3 次比较才能定位，平均一定是中间那个数 2。

最终答案是 C（2）。