从哈希表中删除值的成本是多少？

Question

现在我有一个问题,当我在插入过程中使用线性探测时,我被问到从哈希表中删除值的成本.

我可以通过阅读互联网上的各种内容来弄清楚它必须对负载因素做些什么.虽然我不确定,但是我读了加载因子和所需探针之间的关系,它是探针No = 1 /(1-LF).

所以我认为成本必须取决于探针序列.但是,另一个想法毁了一切.

如果元素插入p探针中,现在我试图删除此元素,该怎么办？但在此之前,我已经删除了几个具有相同哈希码的元素,并且是少于p的探针插入的一部分.

在这种情况下,我到达一个阶段,我在哈希表中看到一个空的空格但我不确定我试图删除的元素是否已经被删除或者是因为探测而在某个其他位置.

我还发现,一旦我删除了一个元素,我必须用一些特殊的指示符来标记这个插槽,以告知它是可用的,但这并不能解决我不确定我愿意删除的元素的问题.

有人可以建议如何在这种情况下找到费用吗？如果是非线性探测,方法是否会发生变化？

Answer 1

标准方法是"查找元素,标记为已删除".标记显然具有O(1)成本,因此总操作成本与查找相同:O(1)预期.在退化情况下它可以与O(n)一样高(例如,所有元素具有相同的散列).O(1)预期是我们理论上可以说的全部.

关于负载系数.较高负载因子(占用水桶总数的数比),较大的是预期因子(但是这并不改变的理论O开销).请注意,在这种情况下,加载因子包括表元素中存在的数量加上先前标记为已删除的桶数.

其他探测种类(例如二次方)不会改变理论成本,但可能会改变预期的常数因子或其方差.如果你看一下"后备"序列,在线性排序中,不同桶的序列重叠.这意味着如果对于某个桶,序列很长,对于相邻的桶,它也会很长.例如:如果桶4到10被占用,桶#4的顺序是7桶长(4,5,6,...,10),对于#5它是6,依此类推.对于二次探测,情况并非如此.

但是,线性探测具有更好的内存缓存行为,因为您可以检查彼此靠近的内存单元.然而,在实践中,对于二次探测,回退序列很少足够长,因此无关紧要.

最后,在线性探测的情况下,可以在没有删除标记的情况下工作,但为此你必须大大复杂化删除程序(尽管仍然是O(1),但具有更高的常数因子).是否值得,必须通过实际剖析来决定; 例如,这简化了插入并略微查找.但是对于C++实现,这将有一个缺点,即erase()会使迭代器无效.