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