题目

现有长度为 11 且初始为空的散列表 HT，散列函数是 ，采用线性探查(线性探测再散列)法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次插入到 HT 后，HT 查找失败的平均查找长度是( )。

错因

A

把分母用错，按""（除以表长 11）算：，再四舍五入到 4。但是 的值域只能是 ，分母应该是 7，不是表长 11。

B

可能用 （除以已插入的元素个数 8）。这是把分母混成了"成功查找"的分母——成功查找的 ASL 才以 n（关键字数）为分母，失败查找应该以 的值域大小为分母。

D

，等价于在求和里多算了一个起点。例如把 也当作可能的散列地址，加上"从位置 7 开始探查到位置 8 是空"算 2 次，得 。但 的值域是 ，根本不会从 7 开始查。

总解析

ASL 失败定义：对每个可能的散列地址 （k 是 H 的值域大小），从位置 h 开始线性探查，直到第一个空槽为止的比较次数的平均。"碰到空槽"的那一次比较也算 1 次。

步骤 1：依次插入并跟踪散列表状态。

关键字		实际位置
87	3	3
40	5	5
30	2	2
6	6	6
11	4	4
22	1	1
98	0	0
20	6（冲突）	7（探到下一空位）

最终散列表状态（位置 8、9、10 为空）：

位置	0	1	2	3	4	5	6	7	8	9	10
值	98	22	30	87	11	40	6	20	–	–	–

步骤 2：对每个起始地址 h ∈ {0,1,2,3,4,5,6}，从位置 h 开始往后线性探查，直到遇到第一个空槽（位置 8）为止：

h	探查路径	比较次数
0	8 空	9
1	8 空	8
2	8 空	7
3	8 空	6
4	8 空	5
5	8 空	4
6	8 空	3

步骤 3：对所有 7 个可能起点取平均：

最终答案是 C。