哈希表：开放地址和删除元素

Question

我正在努力理解散列表中的开放地址方法，但我的文献中没有回答一个问题。这个问题涉及到使用二次探测法删除这样一个哈希表中的元素。然后删除的元素被替换为一个哨兵元素。get()操作就知道它必须继续前进，add()方法将覆盖它找到的第一个哨兵。但是，如果我想要添加一个已经在散列表中且位于探测路径上哨兵后面的键的元素会发生什么？与其覆盖已经在表中具有相同键的实例的值，add()方法将覆盖哨兵。然后，我们在哈希表中有多个具有相同键的元素。我认为这是一个问题，因为它会浪费内存，并且由于从散列表中删除元素只能删除它们中的第一个，因此仍然可以在表中找到该元素（即未被删除）。

因此，在替换哨兵元素之前，似乎有必要搜索整个探测路径以查找要插入的元素的键。我是否忽视了某些东西？这个问题在实践中如何处理？

- j0ker

Answer 1

但是，如果我想添加一个具有已经存在于散列表中但位于探测路径中的标志符后面的键的元素会发生什么情况？add()方法不会覆盖已经在表中的具有相同键的实例的值，而是会覆盖标志符。

正如您后来指出的那样，add()必须检查探测路径中标记符后面的每个元素，直到找到一个空元素。如果它无法在探测路径中找到新元素并且其中有标记符元素，则可以使用第一个标记符插槽来存储新元素。 http://www.algolist.net/Data_structures/Hash_table/Open_addressing上有一个哈希表实现（HashMap.java）。它的put()方法正好做到了这一点。（所引用的片段中的冲突解决是线性探测，但我认为从算法的角度来看，这并不是一个重要的区别。）

在进行大量删除操作后，散列表中可能会有太多的哨兵元素。解决方法是偶尔重建哈希表（即重新对所有内容进行哈希），这个操作将消除哨兵元素（sentinel elements）。

另一种方法是在删除元素时从探测路径中消除哨兵（DELETED）元素。实际上，在这种情况下，表中没有哨兵元素；只有FREE和OCCUPIED插槽。但这可能很费钱。

因此，在替换哨兵元素之前，似乎有必要搜索整个探测路径以查找所需插入元素的键。

是的，确实如此。您必须搜索直到找到一个空元素。

这个问题在实践中如何处理？

我对实际生活中的哈希表实现不是很了解。我想在开源项目中互联网上有很多这样的实现。我刚刚查看了Java中的Hashtable和HashMap类。两者都使用链式存储而不是开放式地址。

- palacsint

---

谢谢您的回答。我听说Python的字典使用开放寻址法。所以我会去看一下。 - j0ker

Answer 2

抱歉回复晚了，但Java有一个使用开放地址法的哈希表示例：java.util.IdentityHashMap。

此外，您可以使用GNU Trove Project。它的所有映射都是使用开放地址哈希表实现的，详见其概述页面。

- Andrej Fink