对于哈希表，正如我们所熟悉的那样，我们首先计算哈希函数。然后我们需要处理碰撞；当两个或多个键插入散列到同一索引时的情况。执行此操作的两种方法包括单独链接和线性探测。我的问题又是，哪种方法删除成本更低？
我最初的想法是，如果线性探测中的簇很大，并且我们想要在簇中早期删除某些键，则将所有键重新插入到已删除键的右侧可能会变得昂贵。
如果这个陈述完全有效，是否有足够的理由假设单独的链接在删除方面比线性探测更有效？
最佳答案
在线性探测的情况下，删除会影响对具有早于清空单元格的哈希值但存储在晚于清空单元格的位置的其他键的搜索。空的单元格会导致这些搜索错误地报告 key 不存在。因此，当一个单元格被清空时，有必要向前搜索表格中的后续单元格，直到找到另一个空单元格或可以移动到该单元格的键，并且该过程需要继续下去，直到找到一个空单元格。
但是在单独链接的情况下，我们只需要从链表中删除值，并且从链表中删除值比线性探测情况下的上述过程容易得多。
关于java - 如果采用线性探测，删除是否比单独链接的情况更便宜？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58122078/