GESP 七级 · GESP202609 C++ 七级 第 17 题

采用开放定址法处理冲突的哈希表中，删除一个元素后可以直接将该位置置空，不会影响后续查找。

开放定址法的核心是"探测序列"，删除时必须保留这个序列的连续性。不能直接置空，要标记为"已删除"状态，让后续查找能跳过继续探测。

误以为"空位=无元素"。实际上开放定址法的空位是探测终止信号，已删除位是探测继续信号。直接置空会让查找提前终止，漏掉后续同哈希键的元素。

1. 考纲定位

本题考查 GESP 七级《数据结构》模块的哈希表冲突处理。命题人放这道题，就是要卡住那些只背"哈希表用开放定址法解决冲突"这句话，却不懂其内部机制的考生。七级大纲明确要求掌握哈希表的增删查改，但绝大多数学生只记住了插入和查找，删除是最容易被忽略的考点。

2. 解题思维

开放定址法（线性探测/二次探测）的查找逻辑是：从哈希位置开始，沿探测序列逐个检查，直到找到目标或遇到空位（表示该哈希键不存在）。

删除时，如果直接把某个位置置为空，会破坏探测序列的连续性。举例：假设哈希位置 5 存放了键 K1，K1 的哈希值恰好是 5。现在删除 K1，若直接置空，后续查找另一个哈希值也是 5 的键 K2 时，会停在位置 5 这个空位上，认为 K2 不存在，这是错误的。

正确做法是：删除后标记为"已删除"（如用特殊值 -1 或布尔标志），查找时遇到已删除位要继续探测，只有遇到真正的空位才停止。这样探测序列保持完整，查找结果正确。