我不明白为什么 hastable 的 rehash 复杂性在最坏的情况下可能是二次的：
http://www.cplusplus.com/reference/unordered_set/unordered_multiset/reserve/
任何帮助，将不胜感激 ！
谢谢
问问题
2835 次
1 回答
3
只是一些基础知识：
哈希冲突是指两个或多个元素采用相同的哈希。这可能导致最坏情况下的
O(n)操作。我不会真正深入探讨这一点，因为人们可以找到很多解释。基本上所有元素都可以具有相同的散列，因此您将在该散列处拥有一个包含所有元素的大链表（当然，在链表上搜索
O(n)）。它不一定是一个链表，但大多数实现都是这样做的。
重新哈希创建一个具有所需大小的新哈希表，并且基本上对旧表中的每个元素进行插入（可能有更好的方法，但我确信大多数实现不会超过渐近最坏情况的复杂性简单的插入）。
除了上述之外，这一切都归结为这句话：（从这里1）
具有等效值的元素被组合在同一个桶中，并且迭代器（参见 equal_range）可以遍历所有元素。
因此，所有具有等效值的元素都需要组合在一起。为此，在进行插入时，您首先必须检查是否存在具有相同值的其他元素。考虑所有值都采用相同哈希的情况。在这种情况下，您必须查看上述链接列表中的这些元素。所以n插入，通过0, then 1, then 2, then ..., 然后n-1是元素，即0+1+2+...+n-1= n*(n-1)/2= 。O(n2)
你不能优化这个O(n)吗？对我来说，你可以这样做是有道理的，但即使是这样，这并不意味着所有实现都必须这样做。当使用哈希表时，通常假设不会有太多的冲突（即使这个假设是幼稚的），从而避免了最坏情况的复杂性，从而减少了对额外复杂性的需要以使 rehash not take 。O(n2)
1：对于所有可能的仇恨者，很抱歉引用CPlusPlus而不是CPPReference （对于其他所有人 - CPlusPlus 以错误而闻名），但我在那里找不到此信息（所以，当然，它可能是错误的，但我希望它不是，在这种情况下它确实有意义）。
于 2013-08-10T18:55:14.823 回答