📚【高级难度 · 哈希表真题】
“哈希表不是背个公式就行，细节决定成败。”
今天给大家带来一道接近408真题难度的哈希表综合题，融合了：
线性探测冲突处理
平均查找长度（ASL）计算
懒惰删除 vs 物理删除的关键区别
这道题看似常规，但第3、4问暗藏玄机——很多同学在模拟时直接栽跟头！快来自测一下你能拿几分👇
📌 题目回顾
关键字集合：{23, 14, 56, 32, 78, 41, 65, 90}
哈希函数：H(key) = key % 11
哈希表大小：11（地址 0~10）
冲突处理：线性探测法
请回答：
构造哈希表，写出每个关键字的最终地址；
计算等概率下成功查找的平均查找长度（ASL）；
若懒惰删除 56后插入 12，12 存在哪？
若物理删除 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差异
删除操作对后续插入/查找的结构性影响
装填因子与性能的关系
✅你答对了几问？
欢迎在评论区晒出你的答案！
如果觉得有收获，点赞+转发给一起备考的小伙伴吧！
