工作兩年中，關于查找敏感型的代碼不少用到了hash_map，關于它的實現細節和需要注意的地方這里梳理一下。因為工作在linux環境下，所以這里hash_map的評述都是根據SGI的源碼。
hash_map說簡單一點就是一個hashtable桶和對于這個桶基本操作的再次封裝。即包含(圖片太麻煩，文字代替吧)：1、_Hashtable* _M_ht;2、erase()、find()等函數。對應的iterator包含：1、_hashtable* _M_ht(這個就是hash_map中的hashtable指針);2、_Node* _M_cur(指向當前hashtable桶的某個節點)。_Node的結構為：
template <class _Val>
struct _Hashtable_node
{
_Hashtable_node* _M_next;
_Val _M_val; //桶的節點，具體是實現使用的Vector，后面有介紹
};
所以hash_map的實現主要是hashtable的實現。下面看一下hashtable的組成(private成員)：
hasher _M_hash; //hasher，處理沖突時用到的，是hashtable性能如何的關鍵因素之一
key_equal _M_equals;//鍵值是否相等的函數，std::string等非基本數據類型做鍵值時需要提供此函數
_ExtractKey _M_get_key;//和Alloc相關的函數
_Vector_type _M_buckets;//hashtable桶的基本元素，SGI實現是 vector<_Node*, _Nodeptr_Alloc>
size_type _M_num_elements;//標示hashtable元素個數，size()函數返回的即是此值
撇去具體實現細節，hashtable基本上也就這些內容(基本也就是一個很大的vector，每個vector節點掛著一個形同list存放沖突節點)。
插入(方法有insert和operator[])過程：
- 調用resize() 判斷是否調整桶的大小，桶的不同大小SGI實現是很有講究的，具體參見__stl_prime_list 數組
- 得到key 通過_M_bkt_num(__obj)
- 通過hash函數得到hash值 通過_M_hash(__key)
- 得到桶號(一般都為hash值對桶數求模) 通過_M_hash(__key) % __n
- 存放key和value在桶內。
取值(find后通過iterator或者operator[])過程:
- 得到key _M_bkt_num_key(__key)
- 通過hash函數得到hash值 通過_M_hash(__key)
- 得到桶號(一般都為hash值對桶數求模) 通過_M_hash(__key) % __n
- 比較桶的鏈表上元素是否與key相等，若都不相等，則沒有找到。
- 取出相等的記錄的value。 find()方法返回 iterator(__first, this)
下面再說說iterator的操作，因為它是比較容易出錯的。
begin()操作是用一個for循環，在hashtable上面的vector里找到第一個即_M_buckets[__n]指針不為空的 iterator(_M_buckets[__n], this)
end()操作返回 iterator(0, this)
operator++ 操作是從_M_cur開始，優先_M_cur->_M_next，為空時遍歷vector直至找到一個_M_cur不為空的節點
迭代器操作使用不當，很容易出問題，hash_map的也不例外，具體看后面代碼例子。
注意到hash_map默認的構造函數
hash_map()
: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
默認是初始化一個100個hashtable桶元素，如果你的hash_map用不到這么多元素，建議不要使用默認值。
hash_map的鍵值一經插入，使用期間不要更改(有時候時內存釋放等造成的)，否則會釀造悲劇，如下例：
/**
*\author peakflys
*\brief 演示hash_map鍵值更改造成的問題
*/
#include <iostream>
#include <ext/hash_map>
struct Unit
{
char name[32];
unsigned int score;
Unit(const char *_name,const unsigned int _score) : score(_score)
{
strncpy(name,_name,32);
}
};
int main()
{
typedef __gnu_cxx::hash_map<char*,Unit*> uHMap;
typedef uHMap::value_type hmType;
typedef uHMap::iterator hmIter;
uHMap hMap;
Unit *unit1 = new Unit("peak",100);
Unit *unit2 = new Unit("Joey",20);
Unit *unit3 = new Unit("Rachel",40);
Unit *unit4 = new Unit("Monica",90);
hMap[unit1->name] = unit1;
hMap[unit2->name] = unit2;
hMap.insert(hmType(unit3->name,unit3));
hMap.insert(hmType(unit4->name,unit4));
for(hmIter it=hMap.begin();it!=hMap.end();++it)
{
std::cout<<it->first<<"\t"<<it->second->score<<std::endl;//正常操作
}
for(hmIter it=hMap.begin();it!=hMap.end();++it)
{
Unit *unit = it->second;
//hMap.erase(it++);
delete unit; //delete釋放節點內存，但是hMap沒有除去,造成hMap內部錯亂，有可能宕機
}
hmIter it = hMap.begin();
strncpy(it->first,"cc",32);//強行更改
for(hmIter it=hMap.begin();it!=hMap.end();++it)
{
std::cout<<it->first<<"\t"<<it->second->score<<std::endl;//死循環，原因參加上面++操作說明
}
return 0;
}
上面錯誤都是實際使用時很容易遇到的情況。暫時先寫到這里，VS下的hash_map的實現和SGI的相差比較大，例如hashtable動態大小的調整是完全按照vector2倍的策略增長等等。
原創內容，轉載注明作者和出處，謝謝。