为什么rehash具有二次复杂度，而operator []在最坏情况下具有线性复杂度？

Question

我知道这个问题，但我的有点不同。

为什么

rehash

具有二次复杂度，而

operator []

（可以调用

rehash

）在最坏情况下具有线性复杂度？

抱歉，但是我没有 10 分来添加图像，所以如果当你看到这个问题时一切都已经解决了，这是我在 cppreference 中看到的：

rehash

复杂性：

平均情况与容器大小呈线性关系，最坏情况与容器大小呈二次关系。

operator[]

复杂性：

平均情况：恒定，最差情况：大小呈线性。

我知道为什么 rehash 可以具有二次复杂度。然而，使其成为线性并不困难。因此，任一陈述都可以为真，但不能同时为真（仅当意味着不同的大小时，但我不明白什么可以被视为大小，除了元素的数量）。

Answer 1

确实不清楚为什么标准要求

rehash

仅是二次最坏情况，而不是

unordered_map

呈线性。

正如链接问题中提到的，

equal_range

的

unordered_multimap

函数的存在使得

rehash

成为二次最坏情况，但这是因为

unordered_multimap

需要在新存储桶中按顺序查找每个插入键的插入键将其放置在可能存在的相同键元素附近。因此，对于具有所有不同键的映射，并且恰好将所有键重新散列到同一个存储桶中，映射将需要对所有存储桶元素进行线性搜索。

另一方面，

unordered_map

已经知道所有键都是唯一的，因此它可以将重新散列的元素插入到桶链的固定位置（例如前面），并且每个元素在 O(1) 时间内完成。由于某种原因，该标准不要求这种行为。

关于

operator[]

，这非常简单：最坏的情况又是当所有密钥都不同时，散列到单个存储桶中，并且您寻找不存在的密钥。您必须查看该存储桶的整个元素链，这将花费相对于容器大小的线性时间。

所以，是的，如果我们记住这种最坏可能散列的病态情况，

rehash

和

operator[]

都渐近地花费相同的时间O（n）其中n是地图元素的数量。它们所做的唯一区别是

operator[]

只是跳过现有的长元素链，而

rehash

构建此链来代替现有的（可能是好的）哈希。