散列：插入已删除的插槽

Question

我是新来哈希，这里是我的问题：

你可以插入哈希表的DELETED插槽吗？

Answer 1

是的，你可以插入到已删除的插槽。但是......

首先，你应该知道，有软删除和硬删除。在软删除中，您只需翻转一个标记并将您的插槽标记为“已删除”，然后在硬删除时清空插槽。

让我解释一下为什么我们需要软删除：例如，你正在使用的哈希表与线性探测，不管怎样你的哈希函数映射3个的输入值相同的插槽。通过使用线性探测，您可以通过在桌面上线性前进来放置这三个元素，直到找到一个空插槽。如果您使用硬删除删除这种情况下，你会打破哈希表，因为会有一个空的插槽，同时尝试检索值，因此一个值将无法访问。

另一方面，如果你有一个完美的散列函数，你可以使用硬删除。完美的散列函数将每个输入值唯一地映射到插槽。所以不需要探测方案，硬删除不会破坏你的表格。

现在回到你的问题，你也应该考虑，并找出如何避免重复插入。