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

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

一种简单的技术是:

查找并删除所需的元素

转到下一个桶

如果桶是空的,退出

如果存储桶已满,请删除该存储桶中的元素,然后使用常规方法将其重新添加到哈希表中.在重新添加之前必须删除该项目,因为该项目可能会被添加回其原始位置.

重复步骤2.

这种技术可以保持您的表整洁,但代价是删除速度稍慢.

这取决于你如何处理溢出以及(1)被删除的项目是否在溢出槽中,以及(2)如果除了项目之外还有溢出项目,是否有被删除项目的哈希键或者可能是其他一些哈希键.[忽略这种双重条件是删除实现中常见的错误来源.]

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

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

Knuth给出了一个很好的结果,如算法R6.4 [pp.相反,它将单元格标记为空而不是删除,然后通过移动刚刚制作的孔直到它最终靠近另一个孔,找到将表条目移回其初始探针位置的方法.

Knuth警告说,这将移动现有的仍然占用的插槽条目,如果指向插槽的指针被保留在散列表的外部,则不是一个好主意.[如果您在插槽中有垃圾收集或其他托管引用,则可以移动插槽,因为它是在表外使用的引用,并且引用的插槽位置无关紧要同一个对象在表中.]

Python哈希表实现(可以说得非常快)使用虚拟元素来标记删除.随着你的成长或缩小或表(假设你没有做一个固定大小的表),你可以同时丢弃假人.

如果您有权访问副本,请查看Beautiful Code中有关实现的文章.