根据hash_map的实现进行理论猜测,不设初始bucket数时,插入是会比较慢的。
实际测试证实如果设置合适的初始bucket数效率较高,快1倍左右。
============================================
不设初始bucket数时
#include <map>
#include <ext/hash_map>
#include <time.h>
using namespace __gnu_cxx;
using namespace std;
const unsigned item_cnt = 1000000;
int main()
{
clock_t start, finish;
start = clock();
hash_map<unsigned, unsigned> hashMap; //不设bucket数,构造空hash_map
unsigned i;
for(i = 0; i < item_cnt; i++)
hashMap[i] = i;
finish = clock();
printf( "cnst and insert time: %f seconds\n", (double)(finish - start) / CLOCKS_PER_SEC);
start = clock();
for(i = 0; i < item_cnt; i++)
if(hashMap.find(i) == hashMap.end())
printf("error: item not found\n.");
finish = clock();
printf("size: %u\n", hashMap.size());
printf("max_size: %u\n", hashMap.max_size());
printf("bucket_size: %u\n", hashMap.bucket_count());
printf( "search time: %f seconds\n", (double)(finish - start) / CLOCKS_PER_SEC);
return 0;
}
[ljl@tcdzq cplus]$ g++ -o hash.out hash_map.cpp
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.000000 seconds
size: 10000
max_size: 4294967295
bucket_size: 12289
search time: 0.000000 seconds
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.000000 seconds
size: 10000
max_size: 4294967295
bucket_size: 12289
search time: 0.010000 seconds
[ljl@tcdzq cplus]$ g++ -o hash.out hash_map.cpp
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.100000 seconds
size: 100000
max_size: 4294967295
bucket_size: 196613
search time: 0.020000 seconds
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.100000 seconds
size: 100000
max_size: 4294967295
bucket_size: 196613
search time: 0.020000 seconds
[ljl@tcdzq cplus]$ g++ -o hash.out hash_map.cpp
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.930000 seconds
size: 1000000
max_size: 4294967295
bucket_size: 1572869
search time: 0.220000 seconds
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.930000 seconds
size: 1000000
max_size: 4294967295
bucket_size: 1572869
search time: 0.220000 seconds
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
=================================
设初始bucket数时
#include <map>
#include <ext/hash_map>
#include <time.h>
using namespace __gnu_cxx;
using namespace std;
const unsigned item_cnt = 1000000;
int main()
{
clock_t start, finish;
start = clock();
hash_map<unsigned, unsigned> hashMap(item_cnt);
//hash_map<unsigned, unsigned> hashMap((unsigned)(item_cnt * 1.5)); //与上行的测试结果一样
unsigned i;
for(i = 0; i < item_cnt; i++)
hashMap[i] = i;
finish = clock();
printf( "cnst and insert time: %f seconds\n", (double)(finish - start) / CLOCKS_PER_SEC);
start = clock();
for(i = 0; i < item_cnt; i++)
if(hashMap.find(i) == hashMap.end())
printf("error: item not found\n.");
finish = clock();
printf("size: %u\n", hashMap.size());
printf("max_size: %u\n", hashMap.max_size());
printf("bucket_size: %u\n", hashMap.bucket_count());
printf( "search time: %f seconds\n", (double)(finish - start) / CLOCKS_PER_SEC);
return 0;
}
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$ g++ -o hash.out hash_map.cpp
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.470000 seconds
size: 1000000
max_size: 4294967295
bucket_size: 1572869
search time: 0.210000 seconds
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.460000 seconds
size: 1000000
max_size: 4294967295
bucket_size: 1572869
search time: 0.220000 seconds
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$ g++ -o hash.out hash_map.cpp
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.040000 seconds
size: 100000
max_size: 4294967295
bucket_size: 196613
search time: 0.020000 seconds
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.040000 seconds
size: 100000
max_size: 4294967295
bucket_size: 196613
search time: 0.020000 seconds
[ljl@tcdzq cplus]$
[ljl@tcdzq cplus]$ g++ -o hash.out hash_map.cpp
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.000000 seconds
size: 10000
max_size: 4294967295
bucket_size: 12289
search time: 0.000000 seconds
[ljl@tcdzq cplus]$ ./hash.out
cnst and insert time: 0.000000 seconds
size: 10000
max_size: 4294967295
bucket_size: 12289
search time: 0.000000 seconds
[ljl@tcdzq cplus]$
分享到:
相关推荐
关于hash_map的用法与解释: #include <hash_map> #include #include using namespace std; //define the class class ClassA{ public: ClassA(int a):c_a(a){} int getvalue()const { return c_a;} void ...
hash_map
linux 下hash_map的基本原理及使用,希望对大家有帮助。
代码重点是hash_table,附加std::map与其做对比,实现的是一条sql语句:select c_nationkey, c_mktsegment, count(*), max(c_acctbal) from aaa_customer_1g group by c_nationkey, c_mktsegment order by c_...
一个用Hash算法实现的map,可以实际项目所使用。 希望能帮助大家学习。
TBB 并发容器 concurrent_queue concurrent_vector concurrent_hash_map TBB 并发容器 concurrent_queue concurrent_vector concurrent_hash_map TBB 并发容器 concurrent_queue concurrent_vector concurrent_hash_...
本实例实现了一个hash_map,key是string类型,即可以存储索引是string的数据,希望对大家有帮助
jg :: dense_hash_map 一个简单的std::unordered_map替代品,具有更好的性能,但失去了稳定的寻址方式,这是一种折衷方案。 在此处查看此哈希图的详细说明: : 生成状态: 特拉维斯(Travis):
结合Java的HashMap中的一些优点,改进了C++ 的hash_map。 详细说明见我的博客:http://blog.csdn.net/mdj67887500/article/details/6907702
hash_map基于hash table(哈希表)。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间...
但是对于hash表来说,由于无法避免re-hash所带来的性能问题,即使大多数情况下hash表的性能非常好,但是re-hash所带来的不稳定性在当时是不能容忍的。 不过由于hash表的性能优势,它的使用面还是很广的,于是第三方...
hash表操作函数 HASH_ADD_INT HASH_ADD_STR
hash_map 的成员函数实现: size_t hash (const Key& key); size_t size(); iterator begin(); iterator end(); iterator rbegin(); iterator rend(); iterator insert (const Key& key, const Value& value); ...
Hash值查看以及修改软件(Hash_1.0.4_0523.exe以及HashModifier.exe),网盘必备工具。
混沌加密算法与HASH函数构造研究_12767438.zip
Hash_1.0.4.exe检验文件Hash,
文件MD5查看 Hash_1.0.4_XiaZaiBa.exe
MD5校验Hash_1.0.4 轻松复制各个参数 检验软件安全性
Hash函数代码,便于结合原理与实践。你可以下载后学习,更希望你能分享出更好的代码
stm32f407平台上实现的hash算法