一、简介

就应用来说，map已经是STL标准库的成员，而hash_map暂时还未进入标准库，是扩展ext中的一个功能，但也是非常常用并且非常重要的库。

二、简单对比

首先，要说的是这两种数据结构的都提供了KEY-VALUE的存储和查找的功能。但是实现是不一样的，map是用的红黑树，查询时间复杂度为log(n)。而hash_map是用的哈希表，查询时间复杂度理论上可以是常数，但是消耗内存大，是一种以存储换时间的方法。

树查找，在总查找效率上比不上hash表，但是它很稳定，它的算法复杂度不会出现波动。在一次查找中，你可以断定它最坏的情况下其复杂度不会超过O(log2N)。而hash表就不一样，是O(1)，还是O(N)，或者在其之间，你并不能把握。

三、hash_map的使用

可见，如果定义完整的hash_map，需要提供<key类型，value类型，哈希函数，key相等判断函数，value类型内存分配器>等5个模板参数，由于后三个都有默认值，所以一般我们只需要提供前两个。

1> 定义__gnu_cxx::hash_map<string, int> myHashMap不会出错，然而一旦对myHashMap进行操作，就会出现编译错误“instantiated from here”，这是因为gnu版本的hash_map只实现了有限的几个hash模板函数（见第三个模板参数，这些函数在hash_fun.h中），而这些函数里包括hash<const char*>，但是不包括hash<std::string>的实例化。解决办法是定义哈希表前自己特化一个实例，这样编译器就知道调用这个函数了。

namespace__gnu_cxx{template<>structhash<string>{size_toperator()(conststring&s)const{return__stl_hash_string(s.c_str());}};}

2> 第四个参数key相等判断函数的意义

intmain(){__gnu_cxx::hash_map<constchar*,int>myHashMap;charname1[10]="zhu";charname2[10]="zhu";myHashMap[name1]=1;__gnu_cxx::hash_map<constchar*,int>::iteratorit=myHashMap.find(name2);if(it==myHashMap.end())cout<<"notfind"<<endl;return0;}

你会发现，虽然name1和name2都是zhu，但是插入了name1，用name2去查找时，还是查无结果。这是涉及到第四个模板参数，判断key相等，默认的是std::equal_to，而这个函数的定义是用operator==来进行判断的，指针的相等当然就是地址一样了，而name1和name2的地址显然不同。解决办法是用自己指定的函数模板替代默认的。

#include<cstring>#include<iostream>#include<ext/hash_map>#include<backward/hash_fun.h>usingnamespacestd;template<class_Tp>structmy_equal_to:publicbinary_function<_Tp,_Tp,bool>{booloperator()(const_Tp&__x,const_Tp&__y)const{returnstrcmp(__x,__y)==0;}};intmain(){__gnu_cxx::hash_map<constchar*,int,__gnu_cxx::hash<constchar*>,my_equal_to<constchar*>>myHashMap;charname1[10]="zhu";charname2[10]="zhu";myHashMap[name1]=1;__gnu_cxx::hash_map<constchar*,int,__gnu_cxx::hash<constchar*>,my_equal_to<constchar*>>::iteratorit=myHashMap.find(name2);if(it==myHashMap.end())cout<<"notfind"<<endl;elsecout<<it->second<<endl;return0;}

用刚刚特化的hash_map<string, int>就是可以找到的，因为string重载了operator==操作符。

编译使用-Wno-deprecated选项，不然会有backward_warning.h头文件里的告警。

四、肤浅的对比测试(map,系统hash函数的hash_map及自写hash函数的hash_map)

[zhuhuifeng@localhost~]$cat/tmp/name.txt|wc-l25848136#从现有的游戏数据库里拉了561916个角色名(里面本来就有重复的)，然后重复追加了几次，变成了#2584万行的数据

1.系统hash函数的hash_map实现

#include<iostream>#include<fstream>#include<string>#include<ext/hash_map>usingnamespacestd;//特化hash函数的string版本namespace__gnu_cxx{template<>structhash<string>{size_toperator()(conststring&s)const{return__stl_hash_string(s.c_str());}};}//计算当前时间voidcurTime(){time_taTime=time(NULL);structtm*curtime=localtime(&aTime);charctemp[20];strftime(ctemp,20,"%Y-%m-%d%H:%M:%S",curtime);cout<<ctemp<<endl;}intmain(){__gnu_cxx::hash_map<string,int>fileMap;stringtemp;//存放每行的临时字符串inti=0;//统计总个数ifstreamin;in.open("/tmp/name.txt",ifstream::in);if(!in){cout<<"openfilefailed"<<endl;return1;}curTime();//从这里开始计时while(in>>temp){if(fileMap.find(temp)==fileMap.end()){++i;fileMap[temp]=i;}}curTime();//计时结束cout<<i<<endl;in.close();return0;}

#编译[zhuhuifeng@localhost~]$g++-Wno-deprecated3.cpp-ohashMap

2.自写hash函数的hash_map

#include<iostream>#include<fstream>#include<string>#include<ext/hash_map>usingnamespacestd;structstrHash{size_toperator()(conststring&str)const{unsignedlong__h=0;for(size_ti=0;i<str.size();i++)__h=107*__h+str[i];returnsize_t(__h);}};voidcurTime(){time_taTime=time(NULL);structtm*curtime=localtime(&aTime);charctemp[20];strftime(ctemp,20,"%Y-%m-%d%H:%M:%S",curtime);cout<<ctemp<<endl;}intmain(){__gnu_cxx::hash_map<string,int,strHash>fileMap;stringtemp;inti=0;ifstreamin;in.open("/tmp/name.txt",ifstream::in);if(!in){cout<<"openfilefailed"<<endl;return1;}curTime();while(in>>temp){if(fileMap.find(temp)==fileMap.end()){++i;fileMap[temp]=i;}}curTime();cout<<i<<endl;in.close();return0;}

#编译[zhuhuifeng@localhost~]$g++-Wno-deprecated4.cpp-ostrhashMap

3.STL的map

#include<iostream>#include<fstream>#include<string>#include<map>usingnamespacestd;voidcurTime(){time_taTime=time(NULL);structtm*curtime=localtime(&aTime);charctemp[20];strftime(ctemp,20,"%Y-%m-%d%H:%M:%S",curtime);cout<<ctemp<<endl;}intmain(){map<string,int>fileMap;stringtemp;inti=0;ifstreamin;in.open("/tmp/name.txt",ifstream::in);if(!in){cout<<"openfilefailed"<<endl;return1;}curTime();while(in>>temp){if(fileMap.find(temp)==fileMap.end()){++i;fileMap[temp]=i;}}curTime();cout<<i<<endl;in.close();return0;}

#编译[zhuhuifeng@localhost~]$g++2.cpp-omap

4.执行查看结果

[zhuhuifeng@localhost~]$./hashMap#7秒2015-11-0616:25:412015-11-0616:25:48459256[zhuhuifeng@localhost~]$./strhashMap#8秒，和上面的相差无几2015-11-0616:25:502015-11-0616:25:58459256[zhuhuifeng@localhost~]$./map#26秒2015-11-0616:26:022015-11-0616:26:28459256

五、总结

这个测试仅仅是个人娱乐，并没有什么实际价值。最后就是一句话，hash_map是基于hash_table实现的，而hash_table是把以双刃剑，用的好效率很高O(1)，用的不好奔着O(N)就去了。

六、注意hash_map死循环

这个问题简单说来，就是gnu的实现是，内部有个_M_Cur指针指示当前位置A，每次计算operator++，都用当前位置的key调用hash函数计算下一个位置B，如果key传入hash_map以后，又在外部将其内容破坏，导致hash函数计算后的B位置在A位置之前，那么从B到达A以后，又会跳回B，形成B-A区间的死循环。

#include<iostream>#include<cstring>#include<ext/hash_map>usingnamespacestd;intmain(){__gnu_cxx::hash_map<char*,int>hashMap;charname[10]="zhu";hashMap.insert(pair<char*,int>(name,1));strncpy(name,"wang",10);//在外部改变了已经传入hash_map中的key，导致死循环for(__gnu_cxx::hash_map<char*,int>::iteratorit=hashMap.begin();it!=hashMap.end();++it){cout<<it->first<<""<<it->second<<endl;}return0;}