为什么我们不使用布谷鸟散列

Question

我的问题是，据我所知，布谷鸟散列通常需要0(1)时间来插入、删除和查找。最坏的情况是O(1) (摊销)。我的问题是，为什么这个算法没有更多地被使用。为什么我们要使用不同的算法来查找，插入或删除，而不是像布谷鸟散列那样的东西呢？

Answer 1

布谷鸟散列需要无限数量的不同独立散列函数，这与我们通常实现通用散列表的方式不兼容，因为这只需要指定一个散列函数。

如果您正在为特定的数据类型编写哈希表实现，那么可以将哈希函数构建到表实现中，并且布谷鸟哈希可能是合理的。

然而，即使在这种情况下，您也可能无法证明您可以支持任何元素集，因为您的散列函数不是真正的随机和独立的，所以布谷鸟散列实现的插入预期时间为O(1)，但在实际实现中，可能会有一两种情况，它将进入无限循环或失败。

你可以为这样的情况设计一个后备方案，但是布谷鸟散列值得额外的复杂性吗？

当哈希表被提前计算时，布谷鸟哈希可能是完美哈希的一个很好的替代方案……但是如果你是提前做的，那么插入通常不需要那么快，所以你可以使用完美的散列。