在我的实现中，我使用延迟删除和线性或二次探测来解决冲突。对于插入，当我遇到延迟删除的项目时，我将其替换为要插入的项目。这样做有什么缺点或不正确(对于线性或二次或双哈希冲突解决方案)？这不是节省空间吗？
最佳答案
开放地址哈希表的问题是它们的性能会随着时间的推移而下降，尤其是当条目非常动态时。
例如，让我们考虑一个简单的线性探测列表。如果在哈希槽 1 上发生 3 次冲突，则将使用槽 1、2、3。如果 2 被删除，您需要将其标记为“以前使用过”，以便仍然能够在插槽 3 中找到该项目。对于某些使用模式，这会将您的哈希表降级到线性搜索时间越来越长的程度，需要代价高昂的改写以使其再次有效。
当插入/删除大量项目时，关闭寻址哈希表的性能会随着时间的推移更加稳定。但它们对缓存不那么友好，因为您必须摆弄指针。
因此，如果您有几乎不变的键，请使用开放寻址，否则请考虑封闭寻址哈希表。
对于某些问题，您可能还想研究其他概念，例如布谷鸟哈希。
关于data-structures - 哈希表的延迟删除，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13597600/