从哈希表中删除条目的最佳方法

Question

如何最好地从使用线性探测的哈希表中删除一个条目？一种方法是使用标志来指示已删除的元素。是否有比这更好的方法？

- askgelal

Answer 1

一种简单的技术是：

1. 查找并删除所需元素
2. 前往下一个桶(bucket)
3. 如果桶(bucket)为空，则退出
4. 如果桶(bucket)已满，请删除该桶(bucket)中的元素，并使用正常的方式将其重新添加到哈希表中。必须先删除该项，因为该项很可能会被添加回到原始位置。
5. 重复步骤2.

这种技术保持了您的表格整洁，牺牲了稍微慢一些的删除速度。

- Imbue

---

问题在于这可能需要进行一个O(n)操作来填充哈希表中的空洞，其中n是哈希表中插槽数量。 - snibbets

Answer 2

这取决于您如何处理溢出，以及(1)要被删除的项是否在溢出槽中，以及(2)如果除了要被删除的项之外还有溢出项，它们是否具有要被删除的项的哈希键或可能是其他哈希键。[忽略这个双重条件是删除操作实现中常见的错误来源。]

如果冲突溢出到链表中，那就很简单了。您可以弹出列表(可能已经为空)或从链表的中间或末尾删除成员。这些都很有趣，也不是特别困难。还可以进行其他优化，以避免过多的内存分配和释放，使其更加高效。

对于线性探测，Knuth建议一个简单的方法是有一种方式将插槽标记为空、已删除或已占用。将已删除的占用槽标记为删除，以便通过线性探测的溢出跳过它，但如果需要插入，则可以填充第一个跳过的已删除插槽。 [计算机编程艺术，第3卷：排序和搜索，6.4节哈希，第533页(第2版)]。这假设删除操作相当罕见。

Knuth提供了一个很好的改进算法R6.4 [pp. 533-534]，它不是将单元格标记为已删除，而是标记为空，然后找到一种方法，通过移动刚刚创建的空洞来使表条目回到它们的初始探测位置附近，直到它最终靠近另一个空洞。

Knuth警告说，这会移动现有的仍占用插槽条目，并且如果在哈希表之外保持对插槽的指针，这不是一个好主意。[如果插槽中有垃圾收集或其他管理引用，则移动插槽是可以的，因为正在使用的是引用而不是表格外的对象引用，而引用所在的插槽位于表格中的位置并不重要。]

- orcmid

Answer 3

Python的哈希表实现（可以说非常快）使用虚拟元素来标记删除。当你增加、减少或调整表格大小时（假设你不是用固定大小的表格），你可以同时删除这些虚拟元素。

如果您有这篇文章的副本，请查看《编写优美代码》中关于Python哈希表实现的文章。

- Tony Arkles

Answer 4

我能想到的最好的通用解决方案包括：

• 如果可以使用非const迭代器（例如C++ STL或Java），则在遇到它们时应该能够将它们删除。然而，假设底层集合被修改后枚举器会失效，你才会提出这个问题。
• 如你所说，你可以在包含的对象中标记已删除的标志。但是，这并不释放任何内存或减少键上的冲突，因此这不是最佳解决方案。此外，需要在类上添加一个属性，这可能并不真正属于那里。如果这让你像我一样困扰，或者如果你根本无法向存储对象添加标志（也许你无法控制该类），则可以将这些标志存储在单独的哈希表中。这需要最长期的内存使用。
• 在遍历哈希表时，将要删除的项的键推入向量或数组列表中。在释放枚举器后，循环遍历此次要删除的列表，并从哈希表中删除键。如果要删除的项很多和/或键很大（它们不应该很大），则可能不是最佳解决方案。
• 如果你要从哈希表中删除的项比留在其中的项更多，那么创建一个新的哈希表可能更好。在遍历原始哈希表时，仅向新哈希表中添加要保留的项。然后用新哈希表替换对旧哈希表的引用。这样可以节省次要列表迭代，但只有当新哈希表将比原始哈希表少很多项时才有效，并且当然只有在你可以更改所有对原始哈希表的引用时才有效。
• 如果你的哈希表允许你访问其键的集合，则可以通过这些键进行迭代，并一次性从哈希表中删除项。
• 如果你的哈希表或库中的某个助手提供基于谓词的集合修改器，则可能具有Remove()函数，可向其中传递lambda表达式或函数指针以标识要删除的项。

- P Daddy

Answer 5

当时间是一个因素时，常见的技术是拥有第二个已删除项目的表格，并在有时间时清理主表。在搜索引擎中常用。

- Stephen

Answer 6

将哈希表改进为像链表一样包含指针，这个想法怎么样？ 插入时，如果桶已满，请从此桶创建一个指向存储新字段的桶的指针。

从哈希表中删除内容时，解决方案与从链表中删除节点的编写方式相同。

- user892871