2013-10-22

C++ hash_map(unordered_map)和map性能对比

C/C++语言编程
Views: 18551 | 2 Comments

C++ STL 的 hash_map(unordered_map) 理论上能达到 O(1) 的查找速度, 而 map 是 O(log(N)). 一般会认为, map 比 hash_map 慢, 但是, 具体慢多少呢? 和元素个数有关系吗? 有没有直观的数据?

为此, 我写了一个简单的测试程序, 分别在 100, 1000, 10000, 10000 个元素时, 对两种 map 进行查找, 对比下耗时. 结果如下:

items  type     timespan  timestamp
100    map      +0.432037 1382373147.689263
100    hash_map +0.140390 1382373147.829653
1000   map      +0.672411 1382373197.151690
1000   hash_map +0.152739 1382373197.304429
10000  map      +0.928384 1382373219.558242
10000  hash_map +0.185142 1382373219.743384
100000 map      +1.512256 1382373371.041342
100000 hash_map +0.373361 1382373371.414702

可以看到, 在元素数量较少时(1000 以内), hash_map 的速度是 map 的 3 到 4 倍. 而元素数量达到 10000 或者更多时, hash_map 的速度是 map 的 5 倍. 这就是直观的感受.

补充了插入速度:

100    build_map      +0.001180 1382443114.467226
100    build_hash_map +0.000371 1382443114.467597
1000   build_map      +0.002165 1382443150.065571
1000   build_hash_map +0.001629 1382443150.067200
10000  build_map      +0.012238 1382443170.254071
10000  build_hash_map +0.019952 1382443170.274023
100000 build_map      +0.121713 1382443188.696912
100000 build_hash_map +0.204433 1382443188.901345

可以看到, map 的插入速度比 hash_map 快速, 可以认为是 2 倍.

Related posts:

  1. 构建C1000K的服务器(2) – 实现百万连接的comet服务器
  2. 小心递归次数限制
  3. MySQL”海量数据”查询性能分析
  4. 用PHP遍历SSDB中的zset集合
  5. fdevent – 方便的跨平台IO多路复用接口
Posted by ideawu at 2013-10-22 00:38:17

2 Responses to "C++ hash_map(unordered_map)和map性能对比"

Leave a Comment