一、簡介
就應用來說，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 <>
struct hash<string>
{
size_t operator()(const string &s) const
{ return __stl_hash_string(s.c_str()); }
};
}
2> 第四個參數key相等判斷函數的意義
int main()
{
__gnu_cxx::hash_map<const char *, int> myHashMap;
char name1[10] = "zhu";
char name2[10] = "zhu";
myHashMap[name1] = 1;
__gnu_cxx::hash_map<const char *, int>::iterator it = myHashMap.find(name2);
if (it == myHashMap.end())
cout << "not find" << endl;
return 0;
}
你會發現，雖然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>
using namespace std;
template <class _Tp>
struct my_equal_to : public binary_function<_Tp, _Tp, bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const
{ return strcmp(__x, __y) == 0; }
};
int main()
{
__gnu_cxx::hash_map<const char *, int, __gnu_cxx::hash<const char*>, my_equal_to<const char*> > myHashMap;
char name1[10] = "zhu";
char name2[10] = "zhu";
myHashMap[name1] = 1;
__gnu_cxx::hash_map<const char *, int, __gnu_cxx::hash<const char*>, my_equal_to<const char*> >::iterator it = myHashMap.find(name2);
if (it == myHashMap.end())
cout << "not find" << endl;
else
cout << it->second << endl;
return 0;
}
用剛剛特化的hash_map<string, int>就是可以找到的，因為string重載了operator==操作符。
編譯使用-Wno-deprecated選項，不然會有backward_warning.h頭文件裡的告警。
四、膚淺的對比測試(map,系統hash函數的hash_map及自寫hash函數的hash_map)
[linuxidc@localhost ~]$ cat /tmp/name.txt | wc -l
25848136
#從現有的游戲數據庫裡拉了561916個角色名(裡面本來就有重復的)，然後重復追加了幾次，變成了
#2584萬行的數據
1.系統hash函數的hash_map實現
#include <iostream>
#include <fstream>
#include <string>
#include <ext/hash_map>
using namespace std;
//特化hash函數的string版本
namespace __gnu_cxx
{
template <>
struct hash<string>
{
size_t operator()(const string &s) const
{ return __stl_hash_string(s.c_str()); }
};
}
//計算當前時間
void curTime()
{
time_t aTime = time(NULL);
struct tm * curtime = localtime(&aTime);
char ctemp[20];
strftime(ctemp, 20, "%Y-%m-%d %H:%M:%S" , curtime);
cout<<ctemp<<endl;
}
int main()
{
__gnu_cxx::hash_map<string, int> fileMap;
string temp; //存放每行的臨時字符串
int i = 0; //統計總個數
ifstream in;
in.open("/tmp/name.txt", ifstream::in);
if (!in)
{
cout << "open file failed" << endl;
return 1;
}
curTime(); //從這裡開始計時
while (in >> temp)
{
if (fileMap.find(temp) == fileMap.end())
{
++i;
fileMap[temp] = i;
}
}
curTime(); //計時結束
cout << i << endl;
in.close();
return 0;
}
#編譯
[linuxidc@localhost ~]$ g++ -Wno-deprecated 3.cpp -o hashMap
2.自寫hash函數的hash_map
#include <iostream>
#include <fstream>
#include <string>
#include <ext/hash_map>
using namespace std;
struct strHash{
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 107*__h + str[i];
return size_t(__h);
}
};
void curTime()
{
time_t aTime = time(NULL);
struct tm * curtime = localtime(&aTime);
char ctemp[20];
strftime(ctemp, 20, "%Y-%m-%d %H:%M:%S" , curtime);
cout<<ctemp<<endl;
}
int main()
{
__gnu_cxx::hash_map<string, int, strHash> fileMap;
string temp;
int i = 0;
ifstream in;
in.open("/tmp/name.txt", ifstream::in);
if (!in)
{
cout << "open file failed" << endl;
return 1;
}
curTime();
while (in >> temp)
{
if (fileMap.find(temp) == fileMap.end())
{
++i;
fileMap[temp] = i;
}
}
curTime();
cout << i << endl;
in.close();
return 0;
}
#編譯
[linuxidc@localhost ~]$ g++ -Wno-deprecated 4.cpp -o strhashMap
3.STL的map
#include <iostream>
#include <fstream>
#include <string>
#include <map>
using namespace std;
void curTime()
{
time_t aTime = time(NULL);
struct tm * curtime = localtime (&aTime);
char ctemp[20];
strftime(ctemp, 20, "%Y-%m-%d %H:%M:%S" , curtime);
cout<<ctemp<<endl;
}
int main()
{
map<string, int> fileMap;
string temp;
int i = 0;
ifstream in;
in.open("/tmp/name.txt", ifstream::in);
if (!in)
{
cout << "open file failed" << endl;
return 1;
}
curTime();
while (in >> temp)
{
if (fileMap.find(temp) == fileMap.end())
{
++i;
fileMap[temp] = i;
}
}
curTime();
cout << i << endl;
in.close();
return 0;
}
1
2 #編譯
[linuxidc@localhost ~]$ g++ 2.cpp -o map
4.執行查看結果
[linuxidc@localhost ~]$ ./hashMap #7秒
2015-11-06 16:25:41
2015-11-06 16:25:48
459256
[linuxidc@localhost ~]$ ./strhashMap #8秒，和上面的相差無幾
2015-11-06 16:25:50
2015-11-06 16:25:58
459256
[linuxidc@localhost ~]$ ./map #26秒
2015-11-06 16:26:02
2015-11-06 16:26:28
459256
五、總結
這個測試僅僅是個人娛樂，並沒有什麼實際價值。最後就是一句話，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>
using namespace std;
int main()
{
__gnu_cxx::hash_map<char *, int> hashMap;
char name[10] = "zhu";
hashMap.insert(pair<char *, int>(name, 1));
strncpy(name, "wang", 10); //在外部改變了已經傳入hash_map中的key，導致死循環
for (__gnu_cxx::hash_map<char *, int>::iterator it = hashMap.begin(); it != hashMap.end(); ++it)
{
cout << it->first << " " << it->second << endl;
}
return 0;
}
