现在我有一个问题，当我们在插入过程中使用线性探测时，有人问我从哈希表中删除值的成本。
通过阅读互联网上的各种内容，我发现它必须与负载因子有关。虽然我不确定，但我读到了负载因子和所需探头数量之间的关系，它是探头数量 = 1/(1-LF)。
所以我相信成本必须取决于探针序列。但另一个想法毁了一切。
如果该元素已插入 p 探针中，而现在我试图删除该元素，该怎么办？但在此之前，我已经删除了一些具有相同哈希码的元素，并且是插入小于 p 的探针的一部分。
在这种情况下，我到达了一个阶段，在哈希表中看到一个空槽，但我不确定我尝试删除的元素是否已被删除，或者由于探测而位于其他位置。
我还发现，一旦删除一个元素，我必须用一些特殊的指示符标记这个插槽，以通知它可用，但这并不能解决我不确定我愿意删除的元素的问题。
有人可以建议如何在这种情况下找到费用吗？ 如果是非线性探测，方法会有所不同吗？
最佳答案
标准方法是“查找元素，标记为已删除”。标记显然具有 O(1) 成本，因此总操作成本与查找相同:O(1) 预期。在退化情况下(例如所有元素具有相同的哈希值)，它可能高达 O(n)。理论上我们只能说 O(1) 预期。
关于负载率。负载因子(占用的桶数与总数的比率)越高，预期因子就越大(但这不会改变理论 O 成本)。请注意，在这种情况下，负载因子包括表元素中存在的数量加上之前标记为已删除的存储桶的数量。
其他探测类型(例如二次)不会改变理论成本，但可能会改变预期的常数因子或其方差。如果你看一下“后备”序列，在线性排序中，不同桶的序列会重叠。这意味着如果对于某个桶来说序列很长，那么对于相邻的桶来说它也会很长。例如:如果桶 4 到 10 被占用，则桶 #4 的序列是 7 个桶长(4, 5, 6, ..., 10)，对于 #5 来说是 6，依此类推。对于二次探测，情况并非如此。
但是，线性探测具有更好的内存缓存行为的优点，因为您检查彼此靠近的内存单元。但在实践中，二次探测后备序列很少足够长，因此这一点很重要。
最后，在线性探测的情况下，可以在没有删除标记的情况下工作，但是为此，您必须使删除过程变得相当复杂(尽管如此，预计仍然是 O(1) ，但是使用更高的常数因子)。是否值得，得通过实际分析来决定；例如，这稍微简化了插入和查找。不过，对于 C++ 实现来说，这会有一个缺点，即删除() 会使迭代器无效。
关于hashtable - 从哈希表中删除一个值的成本是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10855989/