测试条件:
gcc version 4.2.1 20070719 [FreeBSD]
FreeBSD 7.2-RELEASE #0: Fri May 1 07:18:07 UTC 2009 root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC amd64
Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 16核
Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 16核
测试程序说明:
先准备好n个字符串随机的MD5字符串做为key,然后分别对3个容器进行插入、遍历、查找、删除操作。
例如,n=100的时候,插入是指插入100个随机MD5 key;遍历是指对容器遍历一次;查找是指分别对这个100个随机的MD5 key做查找操作(即查找100次);删除是指挨个删除这个100个随机MD5 key。
测试数据如下表:
插入,单位us | 100 | 1K | 10K | 100K | 1M | 10M |
std::map | 241 | 2833 | 35888 | 381214 | 4439088 | 62233380 |
std::ext/hash_map | 97 | 1667 | 16466 | 146025 | 1788446 | 18512639 |
std::tr1::unordered_map | 77 | 772 | 8052 | 53094 | 658312 | 7429297 |
遍历,单位us | 100 | 1K | 10K | 100K | 1M | 10M |
std::map | 11 | 76 | 842 | 11603 | 155700 | 1771906 |
std::ext/hash_map | 47 | 430 | 4218 | 39880 | 470344 | 4781575 |
std::tr1::unordered_map | 1 | 1 | 2 | 1 | 2 | 1 |
查找,单位us | 100 | 1K | 10K | 100K | 1M | 10M |
std::map | 156 | 2111 | 30456 | 258709 | 4100260 | 59064394 |
std::ext/hash_map | 77 | 774 | 8056 | 56974 | 660231 | 7705527 |
std::tr1::unordered_map | 77 | 772 | 8051 | 54456 | 659537 | 7600263 |
删除,单位us | 100 | 1K | 10K | 100K | 1M | 10M |
std::map | 291 | 3641 | 49584 | 472414 | 6675897 | 92491113 |
std::ext/hash_map | 89 | 869 | 9068 | 86524 | 964767 | 10372650 |
std::tr1::unordered_map | 49 | 480 | 4879 | 33087 | 395098 | 4369617 |
结论:
1. std::tr1::unordered_map 与 std::ext/hash_map
任何情况下,如果要在这两个容器之间选择的话,我们毫不犹豫应该选择 unordered_map。因为他的性能在上述4中操作中均优于 hash_map,甚至可以说远远优于 hash_map。
2. std::tr1::unordered_map 与 std::map
map的性能总体来说是最差的。但是,当我们需要一个有序的关联容器的时候,我们必须选择std::map,因为 unordered_map 内部元素不是有序的,这一点从名字都可以看出来。除此之外都应该选择 unordered_map 。
3. 上述测试中,unordered_map 的遍历性能几乎是常数级别的,与常识不太相符,需要再研究研究。
附录:贴上源代码
说明:与测试程序稍有区别,这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。
如有错误还请跟帖指出,非常感谢。
- #include <iostream>
- #include <string>
- #include <sstream>
- #include <list>
- #include <map>
- #include <sys/time.h>
- #include <ext/hash_map>
- #include <tr1/unordered_map>
- namespace zl
- { //{{{
- struct equal_to
- {
- bool operator()(const char* s1, const char* s2) const
- {
- return strcmp(s1, s2) == 0;
- }
- };
- struct hash_string
- : public std::unary_function<std::string, std::size_t>
- {
- std::size_t
- operator()(const std::string& __s) const
- #ifdef __linux__
- { return std::tr1::Fnv_hash<>::hash(__s.data(), __s.length()); }
- #else
- { return std::tr1::_Fnv_hash<>::hash(__s.data(), __s.length()); }
- #endif
- };
- struct hash_charptr
- : public std::unary_function<const char*, std::size_t>
- {
- std::size_t
- operator()(const char* __s) const
- #ifdef __linux__
- { return std::tr1::Fnv_hash<>::hash(__s, strlen(__s)); }
- #else
- { return std::tr1::_Fnv_hash<>::hash(__s, strlen(__s)); }
- #endif
- };
- }//}}}
- typedef std::list<std::string> string_list;
- typedef std::map<std::string, int> string_map;
- typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
- typedef std::tr1::unordered_map<std::string, int> string_unordered_map;
- void fill_list(string_list& slist, size_t count);
- uint64_t current_usec();
- int main( int argc, char* argv[] )
- {
- if (argc != 2 && argc != 3)
- {
- fprintf(stderr, "Usage:%s test_count rehash\n", argv[0]);
- fprintf(stderr, "For example:%s 10000 rehash\n", argv[0]);
- return -1;
- }
- size_t count = atoi(argv[1]);
- bool rehash = false;
- if (argc == 3)
- {
- rehash = true;
- }
- string_map smap;
- string_hash_map shash_map;
- string_unordered_map sunordered_map;
- if (rehash)
- {
- sunordered_map.rehash(count);
- }
- string_list slist;
- fill_list(slist, count);
- uint64_t start = 0;
- uint64_t end = 0;
- uint64_t map_insert_us = 0;
- uint64_t hash_map_insert_us = 0;
- uint64_t unordered_map_insert_us = 0;
- uint64_t map_traverse_us = 0;
- uint64_t hash_map_traverse_us = 0;
- uint64_t unordered_map_traverse_us = 0;
- uint64_t map_find_us = 0;
- uint64_t hash_map_find_us = 0;
- uint64_t unordered_map_find_us = 0;
- uint64_t map_delete_us = 0;
- uint64_t hash_map_delete_us = 0;
- uint64_t unordered_map_delete_us = 0;
- // Insert test
- {//{{{
- string_list::iterator it(slist.begin());
- string_list::iterator ite(slist.end());
- //map insert
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- smap[*it] = i;
- }
- end = current_usec();
- map_insert_us = end - start;
- //hash_map insert
- it = slist.begin();
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- shash_map[*it] = i;
- }
- end = current_usec();
- hash_map_insert_us = end - start;
- //unordered_map insert
- it = slist.begin();
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- shash_map[*it] = i;
- }
- end = current_usec();
- unordered_map_insert_us = end - start;
- }//}}}
- // Traverse test
- {//{{{
- //map traverse
- {
- string_map::iterator it(smap.begin());
- string_map::iterator ite(smap.end());
- start = current_usec();
- for (int i = 0; it != ite; ++it)
- {
- i++;
- }
- end = current_usec();
- map_traverse_us = end - start;
- }
- //hash_map traverse
- {
- string_hash_map::iterator it(shash_map.begin());
- string_hash_map::iterator ite(shash_map.end());
- start = current_usec();
- for (int i = 0; it != ite; ++it)
- {
- i++;
- }
- end = current_usec();
- hash_map_traverse_us = end - start;
- }
- //unordered_map traverse
- {
- string_unordered_map::iterator it(sunordered_map.begin());
- string_unordered_map::iterator ite(sunordered_map.end());
- start = current_usec();
- for (int i = 0; it != ite; ++it)
- {
- i++;
- }
- end = current_usec();
- unordered_map_traverse_us = end - start;
- }
- }//}}}
- // Find test
- {//{{{
- string_list::iterator it(slist.begin());
- string_list::iterator ite(slist.end());
- //map find
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- smap[*it] = i;
- }
- end = current_usec();
- map_find_us = end - start;
- //hash_map find
- it = slist.begin();
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- shash_map[*it] = i;
- }
- end = current_usec();
- hash_map_find_us = end - start;
- //unordered_map find
- it = slist.begin();
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- shash_map[*it] = i;
- }
- end = current_usec();
- unordered_map_find_us = end - start;
- }//}}}
- // Delete test
- {//{{{
- string_list::iterator it(slist.begin());
- string_list::iterator ite(slist.end());
- //map delete
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- smap.erase(*it);
- }
- end = current_usec();
- map_delete_us = end - start;
- //hash_map delete
- it = slist.begin();
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- shash_map.erase(*it);
- }
- end = current_usec();
- hash_map_delete_us = end - start;
- //unordered_map delete
- it = slist.begin();
- start = current_usec();
- for (int i = 0; it != ite; ++it, ++i)
- {
- shash_map.erase(*it);
- }
- end = current_usec();
- unordered_map_delete_us = end - start;
- }//}}}
- //stat output
- std::cout << " insert, count " << count << std::endl;
- std::cout << " std::map " << map_insert_us << " us\n";
- std::cout << " std::ext/hash_map " << hash_map_insert_us << " us\n";
- std::cout << "std::tr1::unordered_map " << unordered_map_insert_us << " us\n";
- std::cout << "\n";
- std::cout << " traverse, count " << count << std::endl;
- std::cout << " std::map " << map_traverse_us << " us\n";
- std::cout << " std::ext/hash_map " << hash_map_traverse_us << " us\n";
- std::cout << "std::tr1::unordered_map " << unordered_map_traverse_us << " us\n";
- std::cout << "\n";
- std::cout << " find, count " << count << std::endl;
- std::cout << " std::map " << map_find_us << " us\n";
- std::cout << " std::ext/hash_map " << hash_map_find_us << " us\n";
- std::cout << "std::tr1::unordered_map " << unordered_map_find_us << " us\n";
- std::cout << "\n";
- std::cout << " delete, count " << count << std::endl;
- std::cout << " std::map " << map_delete_us << " us\n";
- std::cout << " std::ext/hash_map " << hash_map_delete_us << " us\n";
- std::cout << "std::tr1::unordered_map " << unordered_map_delete_us << " us\n";
- return 0;
- }
- void fill_list(string_list& slist, size_t count)
- {
- for (size_t i = 0; i < count; ++i)
- {
- std::ostringstream oss;
- oss << i;
- //slist.push_back(MD5::getHexMD5(oss.str().c_str(), oss.str().length()));
- slist.push_back(oss.str());
- }
- }
- uint64_t current_usec()
- {
- struct timeval tv;
- gettimeofday( &tv, NULL );
- return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
- }
相关推荐
但是对于hash表来说,由于无法避免re-hash所带来的性能问题,即使大多数情况下hash表的性能非常好,但是re-hash所带来的不稳定性在当时是不能容忍的。 不过由于hash表的性能优势,它的使用面还是很广的,于是第三方...
jg :: dense_hash_map 一个简单的std::unordered_map替代品,具有更好的性能,但失去了稳定的寻址方式,这是一种折衷方案。 在此处查看此哈希图的详细说明: : 生成状态: 特拉维斯(Travis):
robin_hood::unordered_map和robin_hood::unordered_set是std::unordered_map / std::unordered_set独立于平台的替代品,对于实际的用例而言,它既更快,更高效。 安装及使用 直接纳入 将添加到您的C ++项目。 ...
c++ std stl各容器的应用场合及性能 map hash_map unordered_map multimap list forward_list vector set hash_set multiset unsorted_set queue deque priority_queue
unordered_map和unordered_set的模拟实现 (一)哈希表的特性及概念 定义: 哈希表(Hash table,也叫散列表),是根据关键字值(key,value)直接进行访问的数据结构。也就是说,它通过把关键字映射到表中一个位置来...
替换std::unordered_map , std::unordered_set , std::map和std::set 需要具有C ++ 11支持的编译器,提供了C ++ 14和C ++ 17 API(例如try_emplace ) 非常高效,比编译器的无序映射/集合或Boost或显着更快 ...
其中m1就是⼀个关联数组,为了模拟普通哈希表 (这⾥的所有的都是⽤红⿊树实现的,如果你想⽤哈希表实现,请直接把map替换成hash_map,在空间⾜够的情况下) 另外,如果有C++11⽤,⼀定要⽤unordered_map,别⽤hash_...
《开源》杂志2009年第4期闪亮发布,火热下载中!本期重点文章: 基于互联网的移动应用大势 Linux基金会呼吁厂商...利用unordered_map代替hash_map 怎么安装Fedora10源 Mysql Innodb 引擎优化 邮件系统的选型与架构(上篇)
概念证明(参见 benchmark.cpp)表明,这种映射可以比std::unordered_map快 3 倍。 API 应该很像std::unordered_map ,所以大概的路线图是: 又一个模板类型参数class Pred = std::equal_to 成员函数at 会员...
由于性能优势,使用面广,有许多第三方类库提供了支持,如MSVC中的<hash>和Boost中的,后来Boost的unordered_map被吸纳进了C ++ 11标准。 (1)1.两数之和 译文描述:给你一个数组,要在多个中找到两个数字a和b ,...
并查集实现,带路径压缩和template,高效查找神器!注:库里面如果没有unordered_map,可以换成hash_map或者map
│ │ │ │ │ ├─cc_hash_table_map_ │ │ │ │ │ ├─eq_fn │ │ │ │ │ ├─gp_hash_table_map_ │ │ │ │ │ ├─hash_fn │ │ │ │ │ ├─left_child_next_sibling_heap_ │ │ │ │ ...
实现了创建哈希表的函数 createHashtable,哈希函数 hash,插入键值对的函数 insert,查找键对应值的函数 get,删除指定键的节点的函数 erase,以及打印哈希表的函数 printHashtable。 在 main 函数中进行了简单的...
zhashmap在C ++中快速打开地址的哈希表。 概述此哈希图是一个...这意味着哈希映射可以潜在地替换为std :: map或std :: unordered_map。 该代码支持足够的C ++无序关联容器要求,因此可以代替许多典型的用例。 这些小
它主要是符合“ C ++ unordered_map”的标准,如果下载它,则会发现Visual Studio项目或CMakeLists.txt,其中集成了来自GCC的针对unordered_map的测试套件。 该地图通过的位置。 某个基准:== 1百万次int推送== *...
map − unordered_map (C++11) priority_queue − span (C++20) 其他容器: 顺序 − 关联 无序关联 − 适配器 迭代器库 范围库 (C++20) 算法库 数值库 常用数学函数 特殊数学函数 (C++17) 数值算法 伪随机...
基准测试以下是我的Fortran实施和GCC 4.8标准库之间的基准测试: 对于14个整数数组作为键,将双精度浮点作为值,输入10M: Fortran哈希: 插入:1.80 s 清洁:1.70 s 1.59 GB GCC unordered_map: 插入:2.02 s 清洁...
fatalerror99 array, bind & mem_fn, dynamic_bitset, function, functional/hash, in_place_factory & typed_in_place_factory, lambda, ref, smart_ptr, static_assert, string_algo, type_traits, typeof ...
map(unordered_map) 212 难的 轮胎、回溯、效率优化 堆栈和队列 # 问题 解决方案 困难 相关话题/想法 20 简单的 2020/08/14 日常练习,stack & hash map(unordered_map) 链表和数组 # 问题 解决方案 困难 相关...