关于hash_map的一点感悟

   工作两年中,关于查找敏感型的代码不少用到了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[])过程:
  1. 调用resize()     判断是否调整桶的大小,桶的不同大小SGI实现是很有讲究的,具体参见__stl_prime_list 数组
  2. 得到key   通过_M_bkt_num(__obj)
  3. 通过hash函数得到hash值   通过_M_hash(__key)
  4. 得到桶号(一般都为hash值对桶数求模)    通过_M_hash(__key) % __n
  5. 存放key和value在桶内。


   取值(find后通过iterator或者operator[])过程:
  1. 得到key       _M_bkt_num_key(__key)
  2. 通过hash函数得到hash值   通过_M_hash(__key)
  3. 得到桶号(一般都为hash值对桶数求模)   通过_M_hash(__key) % __n
  4. 比较桶的链表上元素是否与key相等,若都不相等,则没有找到。
  5. 取出相等的记录的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倍的策略增长等等。
   原创内容,转载注明作者和出处,谢谢。

posted on 2012-07-24 14:15 peakflys 阅读(7052) 评论(5)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: 关于hash_map的一点感悟 2012-07-24 15:12 likun

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;//死循环,原因参加上面++操作说明
}

这里会出现死循环的原因能否说明白一点?不是很理解 啊。
只是简单的修改begin()单元里面的内容,怎么会出现这样的现象?  回复  更多评论   

# re: 关于hash_map的一点感悟 2012-07-24 18:29 peakflys

@likun原因很简单,上面我也说过,operator++ 操作是从_M_cur开始,优先_M_cur->_M_next,为空时遍历vector直至找到一个_M_cur不为空的节点,遍历vector时需要取它对应的桶位置(参砍上面hash_map取值过程),_M_bkt_num_key(key)中key的值是修改后的值,假如你改的键值,通过此函数得到的桶位置在你当前元素之前,这样就造成了死循环。  回复  更多评论   

# re: 关于hash_map的一点感悟[未登录] 2012-07-25 12:23 Chipset

有时间试试gcc的unordered_map吧,注意版本号4.6.3以后的,4.6.2版本的哈希表比4.6.3的哈希表处理字符窜时慢的不是一点半点。处理大量字符窜,尤其字符窜很长时,因该比SGI_STL的哈希表快得多。gcc的哈希表处理整数可能比SGI_STL的哈希表要慢,主要是Allocator作怪。  回复  更多评论   

# re: 关于hash_map的一点感悟 2012-08-05 22:39 egmkang

@likun
我跪了.这代码你也写的出啊.  回复  更多评论   

# re: 关于hash_map的一点感悟 2013-05-14 17:38 peakflys

呵呵,这种代码大点的系统,很多都是存在的,而潜在的错误可能还没爆发出来@egmkang
  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

公告

人不淡定的时候,就爱表现出来,敲代码如此,偶尔的灵感亦如此……

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜