我们正在开发一款高性能关键软件，使用 C++ 编写。我们需要一个并发哈希映射表并实现了一个。因此，我们编写了一个基准测试来确定我们的并发哈希映射表与
但是，
编辑:
目前，大多数评论都解释了，可以通过为其预先分配足够的空间来加快unordered_map的速度。在我们的应用程序中，这是不可能的：我们正在开发一个数据库管理系统，需要使用哈希映射在事务期间存储一些数据(例如锁定信息)。因此，这个映射可以是从1(用户只插入一次并提交)到数十亿条记录(如果进行完整表扫描)的任何东西。在这里预先分配足够的空间是不可能的(而且只在开始时分配很多会消耗太多内存)。
此外，我向你道歉，我没有清楚地表达我的问题: 我真正关心的不是使unordered_map变快(使用googles dense hash map对我们来说效果很好)，我只是不太理解这种巨大的性能差异来自哪里。这不能仅仅是预分配的问题(即使有足够预分配的内存，稠密映射的速度也比unordered_map快一个数量级，我们手写的并发映射以大小为64的数组开始-所以比unordered_map小)。
那么
编辑2:
通过分析，我发现很多时间用于整数除法。
编辑3:
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的插入操作似乎非常耗费时间，相比其他映射容器的3-5秒，需要35秒。此外，查找时间似乎也很长。我的问题是：为什么会这样？我在stackoverflow上看到了另一个问题，有人问为什么std::tr1::unordered_map比他自己实现的版本要慢。最高评分的答案中提到，std::tr1::unordered_map需要实现一个更复杂的接口。但我不能理解这个论点：我们在我们的concurrent_map中使用桶(bucket)方法，std::unordered_map也使用桶方法(即google::dense_hash_map没有使用)，但是std::unordered_map至少应该和我们手写的并发安全版本一样快才对吧？除此之外，我在接口中没有看到任何强制执行性能不佳的特性... 所以我的问题是: std::unordered_map是否确实非常慢？如果不是：出了什么问题？如果是：原因是什么。而我的主要问题是：为什么向std::unordered_map插入值如此耗费时间(即使我们在开始时预留了足够的空间，它也不会表现得更好——因此重新哈希似乎不是问题)？编辑:
目前，大多数评论都解释了，可以通过为其预先分配足够的空间来加快unordered_map的速度。在我们的应用程序中，这是不可能的：我们正在开发一个数据库管理系统，需要使用哈希映射在事务期间存储一些数据(例如锁定信息)。因此，这个映射可以是从1(用户只插入一次并提交)到数十亿条记录(如果进行完整表扫描)的任何东西。在这里预先分配足够的空间是不可能的(而且只在开始时分配很多会消耗太多内存)。
此外，我向你道歉，我没有清楚地表达我的问题: 我真正关心的不是使unordered_map变快(使用googles dense hash map对我们来说效果很好)，我只是不太理解这种巨大的性能差异来自哪里。这不能仅仅是预分配的问题(即使有足够预分配的内存，稠密映射的速度也比unordered_map快一个数量级，我们手写的并发映射以大小为64的数组开始-所以比unordered_map小)。
那么
std::unordered_map性能不佳的原因是什么？或者换句话说：是否可以编写std::unordered_map接口的实现，该实现符合标准并且(几乎)与googles dense hash map一样快？还是标准中有些东西强制实施者选择了低效的实现方式吗？编辑2:
通过分析，我发现很多时间用于整数除法。
std::unordered_map使用质数作为数组大小，而其他实现则使用2的幂。为什么std::unordered_map使用质数呢？为了在哈希不好的情况下表现更好吗？对于良好的哈希函数来说，这似乎没有什么区别。编辑3:
inserts: 16462
get : 16978
为什么向std::map中插入比向std::unordered_map中插入更快呢？我是说，啥？std::map具有更差的局部性（树与数组之间），需要进行更多的分配（每次插入相对于每次重哈希+每个冲突加1）并且最重要的是：具有另一种算法复杂度 (O(logn) vs O(1))!