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