对于哈希表，众所周知，我们首先计算一个哈希函数。然后，我们需要注意碰撞；两个或多个要插入的键散列到同一索引的情况。这样做的两种方法包括单独的链接和线性探测。我的问题再次是，删除哪种方法成本更低？
我的最初想法是，如果线性探测中的簇很大，并且我们想在簇中早期删除某些密钥，则将所有密钥重新插入到已删除密钥的右侧可能会变得很昂贵。
此语句，如果完全有效，是否有理由假设单独的链接在删除方面比线性探测更有效？
在线性探测的情况下，删除会影响对哈希值早于清空单元格但存储在清空单元格之后的其他键的搜索。清空的单元格将导致这些搜索错误地报告该密钥不存在。因此，在清空一个单元格时，有必要向前搜索该表的以下单元格，直到找到另一个空单元格或可以移动到该单元格的键为止，并且该过程需要继续进行，直到找到一个空单元格为止。
但是在单独链接的情况下，我们只需要从链表中删除该值，并从链表中删除该值，就比线性探测时的上述过程要容易得多。