线性探测哈希集合：高效检测已插入值（含非哈希索引位置）

针对你遇到的问题，最常用且高效的方案是墓碑标记法（Tombstone），既能保持哈希集合平均O(1)的操作复杂度，又能解决删除后误判重复的问题，具体实现如下：

核心思路 #

删除元素时不直接将位置设为“空”，而是标记为“墓碑”状态。查找或插入时，遇到墓碑需继续向后遍历，直到遇到真正的空位置才停止，这样就能保证不会漏掉哈希冲突后存放在后续位置的元素。

结构体定义 #

把集合条目状态分为三类：空（从未被占用）、墓碑（已删除）、已占用，替代你之前的双bool方案，状态更可靠且内存开销可控：

typedef enum {
    EMPTY,       // 从未存储过元素
    TOMBSTONE,   // 元素已被删除
    OCCUPIED     // 当前存储有效元素
} EntryState;

typedef struct {
    EntryState state;
    void *value;
} set_entry;

关键操作逻辑 #

插入操作 #

1. 计算目标值的哈希索引，从该位置开始遍历哈希表
2. 遍历过程中：
   • 遇到OCCUPIED状态的条目，检查值是否与待插入值相等，若相等则插入失败（避免重复）
   • 遇到EMPTY或TOMBSTONE状态，记录第一个可插入的位置
3. 遍历结束后，若未找到重复值，将第一个可插入位置的状态设为OCCUPIED，存入值

删除操作 #

1. 找到目标元素所在的条目后，不直接将状态设为EMPTY，而是改为TOMBSTONE
2. 无需移动后续元素，避免额外开销

查找操作 #

1. 从哈希索引开始遍历，遇到EMPTY状态时停止遍历（说明目标元素不存在）
2. 遇到OCCUPIED状态则检查值是否匹配，匹配则返回找到
3. 遇到TOMBSTONE状态则继续向后遍历，不能停止

性能保障 #

• 平均情况下，插入、删除、查找仍保持O(1)时间复杂度，仅在最坏场景下退化为O(n)，这是哈希表的固有特性
• 当哈希表负载因子（已占用/墓碑条目数与总容量的比值）超过阈值（通常设为0.7）时，触发扩容操作：创建更大的哈希表，将所有OCCUPIED状态的元素重新哈希插入，此时可完全清理掉墓碑，保证后续操作的效率

这个方案比遍历全表更高效，也比你之前的has_collision方案更可靠——墓碑状态不会因元素删除而失效，内存开销也仅增加一个枚举类型的存储空间，非常实用。

内容的提问来源于stack exchange，提问作者boreddad420