27

从使用线性探测的哈希表中删除条目的最佳方法是什么？一种方法是使用标志来指示已删除的元素？还有比这更好的方法吗？

4

6 回答 6

36

一个简单的技术是：

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

这种技术以稍慢的删除速度为代价使您的表保持整洁。

于 2010-12-09T08:18:28.167 回答
16

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

如果冲突溢出到链表中，这很容易。您要么弹出列表（可能已为空），要么从链接列表的中间或末尾删除成员。这些很有趣，而且不是特别困难。可以进行其他优化来避免过多的内存分配和释放，从而提高效率。

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

Knuth 对算法 R6.4 进行了很好的改进 [pp. 533-534]，而是将单元格标记为空而不是删除，然后通过移动刚刚制作的孔直到它最终靠近另一个孔，找到将表格条目移回更靠近其初始探测位置的方法。

Knuth 警告说，这将移动现有的仍被占用的插槽条目，如果指向插槽的指针被保留在哈希表之外，这不是一个好主意。[如果您在插槽中有垃圾收集或其他托管引用，则可以移动插槽，因为它是在表外使用的引用，并且引用的插槽在哪里都没有关系同一个对象在表中。]

于 2008-11-11T02:06:53.693 回答
10

Python 哈希表实现（可以说非常快）使用虚拟元素来标记删除。随着您的增长或缩小或表格（假设您没有做一个固定大小的表格），您可以同时删除假人。

如果您可以访问副本，请查看Beautiful Code中有关实现的文章。

于 2008-11-11T00:00:26.367 回答
3

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

  • 如果您可以使用非常量迭代器（ala C++ STL 或 Java），您应该能够在遇到它们时将其删除。但是，据推测，除非您使用 const 迭代器或枚举器，否则您不会问这个问题，如果基础集合被修改，它们将失效。
  • 正如您所说，您可以在包含的对象中标记已删除的标志。但是，这不会释放任何内存或减少键上的冲突，因此它不是最佳解决方案。还需要在类上添加一个可能并不真正属于那里的属性。如果这让您和我一样困扰，或者如果您根本无法向存储的对象添加标志（也许您不控制类），您可以将这些标志存储在单独的哈希表中。这需要最长时间的记忆使用。
  • 在遍历哈希表的同时，将要删除的项的键压入向量或数组列表中。释放枚举器后，循环遍历此二级列表并从哈希表中删除键。如果您有很多要删除的项目和/或密钥很大（它们不应该如此），这可能不是最佳解决方案。
  • 如果您最终要从哈希表中删除的项目比您留在那里的项目多，那么创建一个新的哈希表可能会更好，并且当您遍历原始哈希表时，只添加到新的哈希表中你要保留的物品。然后将您对旧哈希表的引用替换为新哈希表。这节省了二次列表迭代，但它可能只有在新哈希表的项目比原始哈希表少得多的情况下才有效，当然，它肯定只有在您可以更改对原始哈希表的所有引用时才有效。
  • 如果您的哈希表允许您访问其键集合，则您可以遍历这些键并一次性从哈希表中删除项目。
  • 如果您的哈希表或库中的某个助手为您提供了基于谓词的集合修饰符，您可能有一个 Remove() 函数，您可以将 lambda 表达式或函数指针传递给该函数以识别要删除的项目。
于 2008-11-11T00:22:46.963 回答
1

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

于 2008-11-20T14:52:01.190 回答
0

如何增强哈希表以包含像链表这样的指针？插入时，如果存储桶已满，则创建一个从该存储桶指向存储新字段的存储桶的指针。

从哈希表中删除某些内容时，解决方案将等同于您编写函数以从链表中删除节点的方式。

于 2014-09-22T22:29:23.287 回答