工作两年中，关于查找敏感型的代码不少用到了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倍的策略增长等等。
原创内容，转载注明作者和出处，谢谢。