1

我有这段代码：

unordered_multiset<int> t;
for (int i = 0; i < 1000000; i++) {
    if (i % 10000 == 0)
        cout << i << endl;

    t.insert(10);
}

所以它只是在一个unordered_multiset. 但是我发现我在哈希中的元素越多，这个工作的速度就越慢？我无法理解原因。在我看来，在应用哈希函数并找到相等元素的桶之后（因为所有相等的元素都组合在一起）stl 只需将它们放在桶的末尾。

那么这里有什么问题呢？

udp：我找到了 unordered_multiset::insert 函数的描述

单个元素插入：平均情况：常数。最坏的情况：容器大小呈线性关系。

所以现在的问题可以改写为：“为什么最坏的情况是线性的”

4

2 回答 2

1

一切都在同一个桶中。要把东西放在桶的末端，你必须找到桶的末端，桶里的东西越多，需要的时间就越长。

于 2015-10-05T07:29:26.803 回答
0

容器尝试通过重新组织存储来平衡自身，以便平均桶大小低于load_factor。它通过添加更多存储桶来实现这一点，希望数据分布更均匀。

当您在所有元素中存储相同的值时，无论如何它们最终都会在同一个存储桶中。哈希表的最坏情况！

于 2015-10-05T07:28:13.857 回答