线性探测哈希集 - 了解值是否已插入的有效方法，只是不在其哈希索引中

Question

我正在用 C 实现一个哈希集，并使用线性探测来处理冲突。我的问题是，当你遇到这样的事情时会发生什么：

1. 一套可容纳32人

2. 值

   a

   的哈希值为14，插入到idx 14

3. 值

   b

   的哈希值为14，与

   a

   冲突，因此它被插入到idx 15

4. 值

   a

   被删除，将 idx 14 留空

5. 值

   c

   ，等于值

   b

   ，具有哈希值14，可以插入到idx 14，因为删除

   a

   后它是空的

正如你所看到的，值

c

不应该被插入到集合中，因为它等于值

b

，但是表中的槽是空的，所以我的程序认为它可以插入，因为缺少搜索对于哈希索引后的

b

。

我的第一个想法是线性搜索整个表以确保插入之前没有重复值，但这消除了集合的 O(1) 插入、删除和查找时间。

我的第二个想法是在表中的每个槽位都有一个这样的结构：

typedef struct {
    bool has_value;
    bool has_collision
    void *value;
} set_entry;

但是，它不仅需要更多的内存，而且

has_collision

的状态也无法真正说出真相，因为值可以从集合中删除。

有更有效的方法吗？

Answer 1

要允许从哈希集中删除元素，您必须能够区分从未使用过的empty槽和在删除其值后可用的freed槽。

要探测哈希表中是否存在某个键，您必须迭代 used 和 freed 槽，仅在 empty 槽上停止。

当您将密钥插入哈希集中时，首先测试它是否存在，如果不存在，则使用其哈希值中的第一个可用（empty或freed）槽。

从哈希集中删除某个键时，如果下一个条目为 empty，则将其条目设置为 empty，否则设置为 freed。如果您可以将条目设置为 empty，您还可以将之前所有连续的 freed 条目设置为 empty。

您不需要额外的布尔字段来跟踪这些状态，如果

value

成员是

void *

，您可以使用2个未使用的指针来表示empty和freed槽，例如哈希表和第二个元素的哈希表。