hash - 为什么 hastable 的 rehash 复杂度在最坏的情况下可能是二次方的

Question

我不明白为什么 hastable 的 rehash 复杂度在最坏的情况下可能是二次的:

http://www.cplusplus.com/reference/unordered_set/unordered_multiset/reserve/

如有任何帮助，我们将不胜感激!

谢谢

Answer 1

只是一些基础知识:

1. 哈希冲突是指两个或多个元素采用相同的哈希。这可能会导致最坏情况下的 O(n) 操作。

   我不会深入探讨这个问题，因为可以找到很多解释。基本上所有元素都可以具有相同的散列，因此您将在该散列处拥有一个包含所有元素的大链表(并且在链表上搜索当然是 O(n) )。

   它不一定必须是链表，但大多数实现都是这样做的。

2. rehash 会创建一个具有所需大小的新哈希表，并基本上为旧表中的每个元素执行插入操作(可能有稍微好一点的方法，但我相信大多数实现都无法超越简单插入的渐近最坏情况复杂度)。

除上述之外，这一切都归结为这条语句:(来自 here ¹)

Elements with equivalent values are grouped together in the same bucket and in such a way that an iterator (see equal_range) can iterate trough all of them.

因此所有具有相同值的元素都需要组合在一起。为此，在执行插入时，首先必须检查是否存在具有相同值的其他元素。考虑所有值都采用相同散列的情况。在这种情况下，您必须查看上述链表中的这些元素。所以 n 插入，查看 0 ，然后是 1 ，然后是 2 ，然后......，然后是 n-1 元素，即 0+1+2+...+n-1 = n*(n-1)/2 = O(n<sup>2</sup>) 。

你不能将其优化为 O(n) 吗？对我来说，您可能能够这样做是有道理的，但即使是这样，这并不意味着所有实现必须以这种方式进行。当使用哈希表时，通常假设不会有太多冲突(即使这个假设是天真的)，从而避免了最坏情况的复杂性，从而减少了对额外复杂性的需求，以使重新哈希不采用 O(n<sup>2</sup>) 。

1:对于所有可能的仇恨者，很抱歉引用 CPlusPlus 而不是 CPPReference(对于其他人 - CPlusPlus 因错误而闻名)，但我在那里找不到此信息(所以，当然，它可能是错误的，但我希望它不是，在这种情况下它确实有意义)。