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