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