hash - 散列：插入已删除的插槽

Question

我是散列新手，这是我的问题：

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

Answer 1

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

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

让我解释一下为什么我们需要软删除：例如，您正在使用带有线性探测的哈希表，并且您的哈希函数以某种方式将 3 个输入值映射到同一个插槽。通过使用线性探测，您可以通过在桌子上线性推进来放置这三个元素，直到找到一个空槽。在这种情况下，如果您使用硬删除进行删除，您将破坏哈希表，因为在尝试检索值时会有一个空槽，因此一个值将变得无法访问。

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

现在回到您的问题，您还应该考虑并弄清楚如何避免重复插入。