关于map和unordered_map还需要知道的

最近在使用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，的确更耗时。