采用线性探测开放定址法的哈希表中，若直接把碰撞簇中间的已删除槽位改成“从未使用”，可能导致后续元素查找提前失败。较合理的删除方式是（）。
开放定址查找依赖连续探测形成的查找链。从未使用的空槽通常表示目标不可能在后面，而已删除槽位不能承担这个终止含义，因此要用墓碑标记区分，保证查找继续。
选项分析
错误。为删除一个元素清空全表既无必要，也破坏所有已有数据。
错误。从未使用的空槽代表探测链终止，不能拿来表示碰撞簇中间的删除位置。
正确。墓碑保持查找链连续，后续插入又可以在满足规则时复用空间。
错误。没有状态信息就无法区分有效元素、删除槽和从未使用槽。
本题为什么容易错
不少同学把开放定址法想成普通数组，觉得删掉就置空。真正的约束来自探测链：中间断开以后，后面的元素还在，却可能再也找不到。
简短答案
开放定址哈希表删除元素时，为什么不能直接把槽位置为空，正确答案是 C（设置已删除墓碑标记，查找继续探测，插入时可按规则复用该槽位）。开放定址查找依赖连续探测形成的查找链。从未使用的空槽通常表示目标不可能在后面，而已删除槽位不能承担这个终止含义，因此要用墓碑标记区分，保证查找继续。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 删除后立即把整个哈希表清空 | 本题干扰项 | 错误。为删除一个元素清空全表既无必要，也破坏所有已有数据。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 把槽位置为从未使用，并规定查找遇到空槽立即成功 | 本题干扰项 | 错误。从未使用的空槽代表探测链终止，不能拿来表示碰撞簇中间的删除位置。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 设置已删除墓碑标记，查找继续探测，插入时可按规则复用该槽位 | 本题正确答案 | 正确。墓碑保持查找链连续，后续插入又可以在满足规则时复用空间。 | 看到题干核心场景时优先联想到它 |
| 只删除关键字，不保留任何槽位状态信息 | 本题干扰项 | 错误。没有状态信息就无法区分有效元素、删除槽和从未使用槽。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 删除后立即把整个哈希表清空：错误。为删除一个元素清空全表既无必要，也破坏所有已有数据。
- 把槽位置为从未使用，并规定查找遇到空槽立即成功：错误。从未使用的空槽代表探测链终止，不能拿来表示碰撞簇中间的删除位置。
- 只删除关键字，不保留任何槽位状态信息：错误。没有状态信息就无法区分有效元素、删除槽和从未使用槽。
知识点详解
开放定址法把冲突元素放在哈希表自身的其他槽位，因此探测序列就是查找路径。普通空槽表示该探测序列从未越过此处，查找可以结束；墓碑只表示原元素被删除，查找必须继续。插入时可记录遇到的第一个墓碑，但通常仍要继续探测以防相同关键字已存在。墓碑过多会拉长探测路径，工程实现可能通过扩容或重散列清理。
备考速记
普通空槽能截断查找，墓碑只能让插入复用，不能让查找停下。
线性探测在线性探测场景中的作用
线性探测在本题中的核心价值，是解决“采用线性探测开放定址法的哈希表中，若直接把碰撞簇中间的已删除槽位改成“从未使用”，可能导致后续元素查找提前失败。较合理的删除方式是（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。
同类题怎么考
- 删除碰撞簇中间元素后，判断某关键字还能否查到。
- 比较链地址法和开放定址法的删除处理。
线性探测在软件设计师软考中的考法
软考选择题通常不会只考概念定义，还会把线性探测放到线性探测场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。
解题思路
举个小例子就清楚了：19、30、41 经同一个散列地址发生冲突，线性排在连续三个槽位。若删掉中间的 30 后把槽位标成普通空槽，查找 41 走到这里会误以为探测链已经结束。墓碑标记告诉查找算法“这里虽然没有有效元素，但后面可能还有同一碰撞簇的数据”，所以要继续走。
考点定位
哈希表槽位不只有占用和空两种状态。开放定址删除时必须区分“从未使用”和“曾使用但已删除”。
易错提醒
- 查找遇到墓碑后立即停止。
- 插入看到第一个墓碑就立刻写入，却没有继续检查后面是否已有相同关键字。
- 把链地址法的链表删除规则直接套到开放定址法。
备考提示
- 画出一个发生连续冲突的小表，分别模拟查找、删除和再次插入。
- 记住三态模型：EMPTY、OCCUPIED、DELETED。
你可能还想了解
- 哈希表删除为什么不能直接置空？
- 墓碑太多会对哈希表性能产生什么影响？
- 开放定址法插入时如何复用已删除槽？
本文小结
开放定址法删除元素时应用墓碑区分“已删除”和“从未使用”。查找遇到墓碑要继续探测，插入可按规则复用，从而避免碰撞簇中间断开。