我们正在用 C++ 开发一个高性能的关键软件。我们需要一个并发哈希映射并实现一个。因此，我们编写了一个基准来确定我们的并发哈希映射与std::unordered_map.
但是，std::unordered_map似乎非常慢......所以这是我们的微基准（对于并发映射，我们产生了一个新线程以确保锁定不会被优化，并注意我从不插入 0，因为我也用google::dense_hash_map,需要一个空值）：
boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max());
std::vector<uint64_t> vec(SIZE);
for (int i = 0; i < SIZE; ++i) {
uint64_t val = 0;
while (val == 0) {
val = dist(rng);
}
vec[i] = val;
}
std::unordered_map<int, long double> map;
auto begin = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
map[vec[i]] = 0.0;
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "inserts: " << elapsed.count() << std::endl;
std::random_shuffle(vec.begin(), vec.end());
begin = std::chrono::high_resolution_clock::now();
long double val;
for (int i = 0; i < SIZE; ++i) {
val = map[vec[i]];
}
end = std::chrono::high_resolution_clock::now();
elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "get: " << elapsed.count() << std::endl;
（编辑：整个源代码可以在这里找到：http: //pastebin.com/vPqf7eya）
结果std::unordered_map是：
inserts: 35126
get : 2959
对于google::dense_map：
inserts: 3653
get : 816
对于我们手动支持的并发映射（它会锁定，尽管基准是单线程的 - 但在单独的生成线程中）：
inserts: 5213
get : 2594
如果我在没有 pthread 支持的情况下编译基准程序并在主线程中运行所有内容，我会为我们的手动支持并发映射得到以下结果：
inserts: 4441
get : 1180
我使用以下命令进行编译：
g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc
因此，特别是插入std::unordered_map似乎非常昂贵 - 35 秒与其他地图的 3-5 秒。查找时间似乎也很长。
我的问题：为什么会这样？我在stackoverflow上阅读了另一个问题，有人问，为什么std::tr1::unordered_map比他自己的实现慢。有最高评价的答案状态，std::tr1::unordered_map需要实现更复杂的接口。但是我看不到这个论点：我们在 concurrent_map 中std::unordered_map使用存储桶方法，也使用存储桶方法（google::dense_hash_map没有，但至少std::unordered_map应该比我们手动支持的并发安全版本一样快？）。除此之外，我在界面中看不到任何强制使哈希映射表现不佳的功能...
所以我的问题是：std::unordered_map看起来很慢是真的吗？如果不是：有什么问题？如果是：那是什么原因。
而我的主要问题是：为什么将一个值插入到std::unordered_map如此可怕的代价中（即使我们一开始就保留了足够的空间，它的性能也不会好很多——所以重新散列似乎不是问题）？
编辑：
首先：是的，提供的基准并不是完美无缺的——这是因为我们用它玩了很多，它只是一个 hack（例如uint64，生成整数的分布实际上不是一个好主意，在循环中排除 0有点愚蠢等等......）。
目前大多数评论都解释说，我可以通过为 unordered_map 预先分配足够的空间来使其更快。在我们的应用程序中这是不可能的：我们正在开发一个数据库管理系统，并且需要一个哈希映射来存储事务期间的一些数据（例如锁定信息）。因此，此映射可以是从 1（用户只需进行一次插入和提交）到数十亿个条目（如果发生全表扫描）的所有内容。在这里预先分配足够的空间是不可能的（刚开始分配很多会消耗太多的内存）。
此外，我很抱歉，我没有足够清楚地说明我的问题：我对快速制作 unordered_map 并不感兴趣（使用谷歌的密集哈希图对我们来说很好），我只是不明白这种巨大的性能差异来自哪里. 它不能只是预分配（即使有足够的预分配内存，密集映射比 unordered_map 快一个数量级，我们的手动支持并发映射从大小为 64 的数组开始 - 所以比 unordered_map 小）。
那么造成这种不良表现的原因是std::unordered_map什么呢？或者换一种方式问：是否可以编写一个std::unordered_map符合标准并且（几乎）与谷歌密集哈希图一样快的接口实现？或者标准中是否有一些东西强制实施者选择一种低效的方式来实施它？
编辑2：
通过分析，我看到大量时间用于整数除法。std::unordered_map使用素数作为数组大小，而其他实现使用 2 的幂。为什么要std::unordered_map使用素数？如果散列不好，性能更好？对于良好的哈希值，恕我直言没有任何区别。
编辑 3：
这些是 的数字std::map：
inserts: 16462
get : 16978
Sooooooo：为什么插入std::map比插入更快std::unordered_map...我的意思是WAT？std::map具有更差的局部性（树 vs 数组），需要进行更多分配（每次插入 vs 每次重新哈希 + 每次冲突加上 ~1），最重要的是：具有另一个算法复杂性（O（logn） vs O（1））！