c++ - 在什么情况下 std::unordered_map 会表现得很慢？

Question

我做了一些随机测试，但无法得出结论。

如果将 1000000 个整数插入到一个 map 和一个 unordered_map 中，map 使用的时间是原来的 3 倍。

如果插入 1000000 个字符串，那么 map 使用的时间是原来的 2 倍。

std::unordered_map 在什么情况下会表现得很慢？

提前致谢。

UPD::gcc 版本 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3)。所有测试都没有-O2。

代码:

a.cpp: std::map<int, int> M;b.cpp: std::unordered_map<int, int> M;

g(i, 1, 1000000) {
    M[i] = rand() % i;
}

我的测试结果:

yyhs@yyhs-Pro:~/Documents$ g++ a.cpp -o a -g --std=c++11 && time ./a

real    0m0.659s
user    0m0.653s
sys 0m0.004s
yyhs@yyhs-Pro:~/Documents$ g++ b.cpp -o b -g --std=c++11 && time ./b

real    0m0.260s
user    0m0.251s
sys 0m0.008s

yyhs@yyhs-Pro:~/Documents$ g++ a.cpp -o a -g --std=c++11 -O2 && time ./a

real    0m0.290s
user    0m0.282s
sys 0m0.008s
yyhs@yyhs-Pro:~/Documents$ g++ b.cpp -o b -g --std=c++11 -O2 && time ./b

real    0m0.081s
user    0m0.081s
sys 0m0.000s

我的问题是什么情况下可能导致 std::unordered_map 变慢。

Answer 1

像往常一样，这将取决于特定的实现，但这并不完全正确，标准保证 std::unordered_map 将渐进地优于 std::map .只有不变的因素会因实现而异。 std::map 的插入时间为 O(log N)，std::unordered_map 的平均插入时间为 O(1)。有关详细信息，请参阅 n3690 中的 §23.4.4.1 和 §23.5.4。

一般来说，std::unordered_map 的性能将大大优于 std::map(如您观察到的那样)，除非您有很多碰撞。您可以通过选择放置在同一个桶中的键来创建冲突。这需要了解您的哈希函数以及从哈希值到存储桶的映射，但是如果攻击者可以控制您的哈希表中的键，则攻击者可以利用这些知识来降低您的程序。因此，在公开的应用程序中使用随机散列函数很常见。

在病态情况下，如果您的哈希函数选择不当(评估速度非常慢或产生许多冲突)，std::map 的性能可能优于 std::unordered_map。这是非常不典型的。

需要注意的是，标准库 std::unordered_map 往往是一个开放的哈希表，以满足 C++ 标准对迭代器行为的要求。众所周知，对于许多应用程序来说，这远非最佳选择，并且有许多替代哈希表库的性能甚至更好。