最近在使用unordered_map的时候遇到几个问题，在此记录下，项目中用户画像数据本来的存储方式是map，因为逻辑中需要每次请求，根据id取value。测试时，当时虚拟机里跑，每次请求计算过程需要200多ms，这个性能是不能接受，我以为是代码性能问题。去尝试用unordered_map存储，但遇到了几个问题。后来发现是当时window好久可能好久没关机，系统略卡，导致虚拟机也卡。
1.unordered_map的查找真的很快吗？
map本质是一个二叉树，二叉树的每次查找是O(lgN),哈希表的查找只是做一个hash计算，然后根据id访问元素，所以它的查找是一个O(1).所以需要频繁查找的使用unordered_map会提升性能，我把上述改为unordered_map了，但是测试结果效率没有升反而降了。我测试了如下代码：
while (i < m) {
map[i] = i + 1;
umap[i] = i + 1;
i++;
}
while(i < n) {
map.find(5);
i++;
}
while (i < n) {
umap.find(1399);
i++;
}
在m=10, n=100000时：
unordered_map cost: 8032
map cost :6852
在m=100, n=100000时：
unordered_map cost: 8572
map cost :10844
我们知道hashmap是平均O(1),map是平均O(lnN)的，实践上并不总是如此，有一下几点需要考虑：
- hashmap的hash算法是不是需要经过复杂的计算。
- 碰撞的次数
一般在数据量小的情况下，unordered_map的性能不如map的。
2.unordered_map的初始化
在代码中.h中定义了一个Feature结构体：
struct Feature {
std::unordered_map<int, int> price;
std::unordered_map<int, int> brand;
std::unordered_map<int, int> seller;
}
替换原来的map后来，发现性能不升反降，就注掉.cc中的代码，但声明局部变量那句忘了注掉。注掉后发现，性能还是没有恢复到修改前的。最后发现注掉这一句后，性能恢复了。我当时的感觉是，这只是一个局部变量而且还没使用的，函数执行完应该就释放了。为啥这么影响性能，然后我写了个测试代码：
auto start = clock();
while (i < 10000) {
std::unordered_map<int, int> umap;
++i;
}
auto end = clock();
std::cout << "unordered_map cost: " << end - start << std::endl;
i = 0;
start = clock();
while (i < 10000) {
std::map<int, int> map;
++i;
}
end = clock();
std::cout<< "map cost :" <<end - start << std::endl;
运行结果：
unordered_map cost: 1994
map cost :423
的确是unordered_map的初始化比较耗时，我们都知道map是红黑树，unordered_map是哈希表，造成性能差异的原因在于，红黑树初始化时，节点只需要一个，后续的插入只是插入新的节点，但是哈希表初始化时就不是那么简单了，哈希表初始化时需要申请一个数组，数组的每个元素都指向一条链表，所以初始化时需要申请很多内存，相比于map，的确更耗时。
网友评论