为什么 Hastable 的重新哈希复杂度在最坏情况下可能是二次的

Question

我不明白为什么 hastable 的重新哈希复杂度在最坏的情况下可能是二次的：

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

任何帮助，将不胜感激 ！

谢谢

Answer 1

只是一些基础知识：

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

   我不会再深入讨论这一点，因为人们可以找到很多对此的解释。基本上所有元素都可以具有相同的散列，因此您将在该散列上有一个包含所有元素的大链接列表（当然，在链接列表上进行搜索O(n)）。

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

2. 重新哈希创建一个具有所需大小的新哈希表，并且基本上为旧表中的每个元素进行插入（可能有一个稍微更好的方法，但我确信大多数实现都不会击败渐近最坏情况的复杂性简单的插入）。

除了上述内容之外，这一切都归结为以下声明：（来自此处¹）

具有相等值的元素被分组在同一个存储桶中，并且迭代器（参见 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 众所周知是错误的），但我在那里找不到此信息（所以，当然，它可能是错误的，但我希望不是这样，在这种情况下它确实有意义）。