hashtable - 哈希表 : Open addressing and removing elements

Question

我试图理解哈希表中的开放寻址，但有一个问题在我的文献中没有得到解答。如果使用二次探查，则涉及删除此类哈希表中的元素。然后被移除的元素被一个哨兵元素替换。然后 get() 操作知道它必须更进一步并且 add() 方法将覆盖它找到的第一个哨兵。但是，如果我想添加一个元素，该元素的键已经在哈希表中，但位于探测路径中的哨兵后面？ add() 方法不是用表中已有的相同键覆盖实例的值，而是覆盖哨兵。然后我们在哈希表中有多个具有相同键的元素。我认为这是一个问题，因为它会消耗内存，而且因为从哈希表中删除元素只会删除它们中的第一个，因此仍然可以在表中找到该元素(即它不会被删除)。

因此，在替换哨兵元素之前，似乎有必要在整个探测路径中搜索想要插入的元素的键。我是否忽略了什么？这个问题在实践中是如何处理的？

Answer 1

But what happens if I want to add an element with a key that is already in the hash table but behind a sentinel in a probing path? Instead of overwriting the value of the instance with the same key which is already in the table, the add() method would overwrite the sentinel.

add()正如您稍后指出的那样，必须检查探测路径中哨兵之后的每个元素，直到找到一个空元素。如果在探测路径中找不到新元素并且上面有哨兵元素，它可以使用第一个哨兵槽来存储新元素。

http://www.algolist.net/Data_structures/Hash_table/Open_addressing上有一个哈希表实现(HashMap.java)。它的 put()方法正是这样做的。 (碰撞解决方案是引用片段中的线性探测，但我认为从算法的角度来看这不是一个重要的区别。)

经过大量的删除操作后，表中可能会有太多的哨兵元素。对此的解决方案是偶尔重建哈希表(即重新哈希所有内容)(基于项目数和哨兵元素数)。此操作将消除哨兵元素。

另一种方法是在删除元素时从探测路径中消除标记 (DELETED) 元素。实际上，在这种情况下，表中没有哨兵元素；只有空闲和占用插槽。它可能很贵。

So it seems that it is necessary to search the whole probing path for the key of the element one wants to insert before replacing a sentinel element.

是的。您必须搜索直到找到一个空元素。

How is this problem handled in practice?

我不太了解现实生活中的哈希表实现。我想它们中的很多都可以在互联网上的开源项目中找到。我刚刚检查了 Hashtable 和 HashMap Java中的类。两者都使用链接而不是开放寻址。