如果使用线性探测，删除的成本是否比单独链接的情况要低？

Question

对于哈希表，正如我们所熟悉的那样，我们首先计算哈希函数。然后我们需要处理碰撞；当两个或多个键插入散列到同一索引时的情况。执行此操作的两种方法包括单独链接和线性探测。我的问题又来了，哪种方法删除成本更低？

我最初的想法是，如果线性探测中的簇很大，并且我们想要在簇中早期删除某些键，则将所有键重新插入到已删除键的右侧可能会变得昂贵。

如果这个陈述完全有效，是否有足够的理由假设单独的链接在删除方面比线性探测更有效？

Answer 1

在线性探测的情况下，删除会影响对具有早于清空单元的哈希值但存储在晚于清空单元的位置的其他键的搜索。空的单元格会导致这些搜索错误地报告密钥不存在。因此，当一个单元格被清空时，有必要向前搜索表格中的后续单元格，直到找到另一个空单元格或可以移动到该单元格的键，并且该过程需要继续下去，直到找到一个空单元格。但是单独链接的情况下，我们只需要从链表中删除值，并且从链表中删除值比线性探测情况下的上述过程容易得多。