题目

将关键字序列 ⟨7, 8, 30, 11, 18, 9, 14⟩ 散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 H(key) = (key × 3) mod 7，处理冲突采用线性探测再散列法，要求装填(载)因子为 0.7。

(1) 请画出所构造的散列表。

(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

解析

预备：算出表长

装填因子 。已填 7 个、，故 表长 m = 10（下标 0..9）。

但散列函数是 ——输出范围是 0..6，不是 0..9。地址 7、8、9 永远不会被 H 直接命中，只能通过线性探测填进去。这是本题的关键陷阱。

(1) 构造散列表

答案：

地址	0	1	2	3	4	5	6	7	8	9
关键字	7	14		8		11	30	18	9

逐次插入推导：

#	key		探查过程	落入
1	7		HT[0] 空	0
2	8		HT[3] 空	3
3	30		HT[6] 空	6
4	11		HT[5] 空	5
5	18		HT[5]=11 冲突 → 6=30 冲突 → 7 空	7
6	9		HT[6]=30 冲突 → 7=18 冲突 → 8 空	8
7	14		HT[0]=7 冲突 → 1 空	1

(2) 平均查找长度（成功 + 不成功）

查找成功 ASL

每个关键字的查找比较次数 = 它当时实际探查路径的长度（从 到落入位置）：

关键字		探查长度
7	0	1（直接命中 HT[0]）
8	3	1
30	6	1
11	5	1
18	5	3（探 5、6、7）
9	6	3（探 6、7、8）
14	0	2（探 0、1）

查找不成功 ASL

按"等概率"约定：目标 key 经 H 计算后等概率落在 0..6（散列函数输出范围共 7 个地址）。从每个起始地址 i 出发线性探测，直到遇到一个空槽为止的比较次数（含遇到空槽那一次）：

起始地址 i	探查序列	比较次数
0	0(7) → 1(14) → 2(空)	3
1	1(14) → 2(空)	2
2	2(空)	1
3	3(8) → 4(空)	2
4	4(空)	1
5	5(11) → 6(30) → 7(18) → 8(9) → 9(空)	5
6	6(30) → 7(18) → 8(9) → 9(空)	4

编者注（生僻术语）：失败 ASL 的分母用 7（散列函数的输出范围 0..6）而不是 10（表长），因为目标 key 通过 H 后第一次探查只可能落在 0..6 这 7 个地址之一——地址 7、8、9 不会被 H 直接命中。这是本题最容易踩的坑。如果题目改成 H = key mod 10，那分母就是 10。