📚【高级难度 · 哈希表真题】

“哈希表不是背个公式就行，细节决定成败。”

今天给大家带来一道接近408真题难度的哈希表综合题，融合了：

• 线性探测冲突处理

• 平均查找长度（ASL）计算

• 懒惰删除 vs 物理删除的关键区别

这道题看似常规，但第3、4问暗藏玄机——很多同学在模拟时直接栽跟头！快来自测一下你能拿几分👇

---

📌 题目回顾

关键字集合：
{23, 14, 56, 32, 78, 41, 65, 90}
哈希函数：H(key) = key % 11
哈希表大小：11（地址 0~10）
冲突处理：线性探测法

请回答：

1. 构造哈希表，写出每个关键字的最终地址；

2. 计算等概率下成功查找的平均查找长度（ASL）；

3. 若懒惰删除 56后插入 12，12 存在哪？

4. 若物理删除 56再插 12，结果一样吗？为什么？

---

✅ 逐问解析（建议先自己做！）

第1问：建表不难，但别算错！

关键字	H(key)	探测路径	最终地址
23	1	1	1
14	3	3	3
56	1 → 冲突	1→2	2
32	10	10	10
78	1 → 冲突	1→2→3→4	4
41	8	8	8
65	10 → 冲突	10→0	0
90	2 → 冲突	2→3→4→5	5

最终哈希表（空位留空）：

[0:65] [1:23] [2:56] [3:14] [4:78] [5:90] [6:] [7:] [8:41] [9:] [10:32]

---

第2问：ASL成功 = 总比较次数 ÷ 元素个数

各关键字查找所需比较次数（等于插入时探测次数）：

• 23(1), 14(1), 56(2), 32(1), 78(4), 41(1), 65(2), 90(4)

• 总和 = 16 → ASL = 16 ÷ 8 = 2.0

✅ 别忘了：ASL成功只看已存在的元素！

---

第3问（易错！）：懒惰删除后插12

• 懒惰删除 = 把地址2标记为 “Deleted”，不是空

• 插入12：H(12)=12%11=1

• 探测路径：1(占) → 2(Deleted，继续！) → 3(占) → 4(占) → 5(占) → 6(空)

🎯 12 存在地址 6

⚠️ 很多人误以为“删了就能插”，但线性探测遇到 Deleted 不会停！

---

第4问（灵魂拷问）：物理删除呢？

• 地址2变成真正的 Empty

• 插12：探到地址2发现是空 → 立刻插入！

🎯 12 存在地址 2

❌ 结果不同！
🔍 原因：物理删除破坏了探测链，可能导致后续元素无法被查到（比如90原本在5，若中间有空洞，查90时会在2停下，找不到！）

这也是为什么开放定址法强烈推荐懒惰删除！

---

💡 考点总结

知识点	是否常考	提醒
线性探测建表	⭐⭐⭐⭐	注意模运算和循环探测
ASL计算	⭐⭐⭐⭐	成功 vs 失败别混淆
删除策略影响	⭐⭐⭐	408近年多次涉及“删除对结构的影响”
懒惰删除原理	⭐⭐	容易忽略，但至关重要

---

📚 小贴士

在408考试中，哈希表题往往以大题形式出现，分值高、步骤多。
务必掌握：

• 不同冲突解决法（线性/二次/链地址）的ASL差异

• 删除操作对后续插入/查找的结构性影响

• 装填因子与性能的关系

---

✅ 你答对了几问？
欢迎在评论区晒出你的答案！
如果觉得有收获，点赞+转发给一起备考的小伙伴吧！

---