企业官网建设流程全解析

📚【中等难度 · 哈希表真题】

（改编自某985高校期末 & 408风格）

已知一组关键字为：

(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79)

哈希表长度为13，采用 除留余数法 构造哈希函数，即：
H(key) = key % 13

请完成以下任务：

（1）若采用线性探测法处理冲突，请：

• 画出最终的哈希表；

• 计算查找成功时的平均查找长度（ASL）。

（2）若采用链地址法处理冲突，请：

• 画出哈希表的存储结构（可用链表图示或文字描述）；

• 计算查找成功时的平均查找长度（ASL）。

（3）比较两种方法在本题中的 ASL，简要说明哪种更适合此数据？为什么？

✅ 参考答案

（1）线性探测法

• 哈希函数：H(key) = key % 13

• 插入过程略（需逐步探测）

• 最终哈希表（地址0~12）：

[0]: ——（空）

[1]: 14

[2]: 1

[3]: 68

[4]: 27

[5]: 55

[6]: 19

[7]: 20

[8]: 84

[9]: 79

[10]: 23

[11]: 11

[12]: 10

各关键字查找长度（探测次数）：19→6（1次），14→1（1次），23→10（1次），1→1→2（2次），68→3（1次），20→7（1次），84→6→7→8（3次），27→1→2→3→4（4次），55→3→4→5（3次），11→11（1次），10→10→11→12（3次），79→1→2→3→4→5→6→7→8→9（9次）

总查找次数=1 + 1 + 1 + 2 + 1 + 1 + 3 + 4 + 3 + 1 + 3 + 9 =30
ASL= 30 / 12 =2.5

（2）链地址法

链表结构：

0:

1: 14 → 1 → 27 → 79

2:

3: 68 → 55

4:

5:

6: 19 → 84

7: 20

8:

9:

10: 23 → 10

11: 11

12:

查找长度： 地址1（4个）：14(1), 1(2), 27(3), 79(4) → 小计：1+2+3+4 = 10 地址3（2个）：68(1), 55(2) → 小计：3 地址6（2个）：19(1), 84(2) → 小计：3 地址7（1个）：20(1) → 小计：1 地址10（2个）：23(1), 10(2) → 小计：3 地址11（1个）：11(1) → 小计：1

总次数= 10 + 3 + 3 + 1 + 3 + 1 = 21

ASL= 21 / 12 = 1.75

（3）比较

• 链地址法 ASL 更小（1.75 < 2.5）；
• 因装填因子高达 0.92，线性探测产生严重聚集；
• 链地址法更适合此场景。