尽量不用char*作为hash_map的key

Posted on 2013-09-09 21:21 Springlie 阅读(83) 评论(0) 编辑 收藏

引子:

同事前几天用hash_map时发现一些问题。当时的场景是有一些字符串char*,要去对应某种类型的对象。同事的做法是:

  • 尝试用char*作为key进行hash。编译通过,但运行时不正常,insert操作可以成功,但find操作基本都失败
  • 改用string将原字符串包装后作为key进行hash。编译时不能通过
  • google后,用string作key,并添加了一个template<> struct hash< std::string >的仿函数作为hash_map的构造参数。编译通过,运行正常,但不知原委为何

带着这三个问题去查看了libstdc++中关于hash_map的实现(省略了与讨论无关部分):

不用char*作为hash_map的key-LMLPHP
 1 // hash_map
2
3 template<class _Key, class _Tp, class _HashFn = hash<_Key>,
4 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
5 class hash_map
6 {
7 private:
8 typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
9 _Select1st<pair<const _Key, _Tp> >,
10 _EqualKey, _Alloc> _Ht;
11
12 _Ht _M_ht;
13
14 // ...
15
16 hash_map()
17 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
18
19 // ...
20
21 _Tp&
22 operator[](const key_type& __key)
23 { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
24
25 // ...
26 }
不用char*作为hash_map的key-LMLPHP

line 3~5 可见,hash_map是个模板类,定义了5种参数类型,分别是

  • key的类型_Key
  • 值的类型_Tp
  • hash仿函数_HashFn,用于执行真正的hash操作。有默认模板参数hash<_Key>
  • 比较仿函数_EqualKey,用于执行hash冲突后,bucket内的find工作。有默认模板参数equal_to<_Key>
  • 内存分配器。有默认模板参数参数

line 8~12可见,hash_map中包含了一个hashtable对象,hashtable也是个模板类,有6个参数类型,参数的具体类型在hashtable.h中,分别是

  • hash_table中储存的值的类型_Val,实际对应hash_map中的pair<const _Key, _Tp>
  • Key的类型_Key
  • hash仿函数
  • 从pair对象中分离出key对象的仿函数_ExtractKey
  • 比较仿函数_EqualKey
  • 内存分配器

line 16~23可见,hash_map其实是对hashtable的包装,其初始化、find与赋值操作都是由内部的hashtable对象来完成的。

hashtable的具体实现是:

  • 由一个bucket数组组成
  • 每个bucket下面挂着一个hash_node组成的list
  • 每个hash_node由一个_Val对象(存储真正元素)和一个hash_node指针(next指针)组成

工作过程是:

  1. 将key用_HashFn进行hash
  2. 将hash的结果执行取模操作%n(其中n是hashtable中bucket的数目),定位到具体bucket的位置
  3. 依次用_EqualKey比较bucket中hash_node的key,找到与输入元素相同的node,返回;若找不到,则构造一个node返回

下面来回答篇首提出的三个问题

为什么用char*(或const char*)作为key,可以顺利insert,却不能顺利find?

因为insert时,会将char*指针进行hash,默认的内置hash函数接受char*作为参数,并将所指字符串进行hash,直到串尾。因此可以顺利找到bucket,但在进一步查找比对key时,用的是equal_to<char*>函数,它是直接比对指针的!一般来说,进行insert操作时,指针是不相同的,因此每次insert都生成新的node返回,insert正确。用size()方法也可以验证到,确实能够insert成功。

而在find操作中(假设用来insert的key已经在hash表中,本应可以命中的),同理可以找到bucket,但是在比对key时用的是char*指针,而实情却是char*所指的内容相同!但equal_to<char*>不会理会这些,它只是傻傻比对指针,因此基本不会找到结果。(假如可以找到结果,那就是hash表中存的char*和你输入的char*正好相同)

为什么改用string作为key,会无法通过编译?

因为默认的内置hash函数不接受string作为参数,也就是说,没有hash(string str)或者hash(const string& str)这种特化存在。其实,hash函数支持的函数是相当有限的,仅有char、int、long以及它们的const和unsigned版本,指针类型更是只支持char*!

为什么加上template<> struct hash< std::string >的实现,就可以编译并执行正确?

首先加上这个hash后,hash函数能够处理string参数,并正确找到bucket,在比对key环节,用的是默认的equal_to<string>,而这个函数可以正确来比对字符串而不是比对指针,因此insert和find都能成功。

至此,总结下以后遇到这种情况怎么办。有两种方法:

  • 写一个关于字符串的比较函数(类似于strcmp就可以),构造hash_map时传进去,保证在key比对时不是对比较指针而是比较字符串
  • 写一个接受string类型的hash函数,保证hash时string参数能被正确处理

事情到此时貌似已经圆满了。连《STL源码剖析》P278也说这样OK。但是……真的是这样吗?char*真的能用来作hash_map的key吗?

答案是不可以,这里存在一个巨大的隐患:

hash表中存储的永远是pair<_Key, _Tp>,如果用char*作key,则存储的key只能是char*。这里就涉及到一个内存管理的问题,你要确保之前insert时用的char*不能失效,而且内容不能被更改。否则在bucket内比对key时就会出现严重的问题,轻则找不到元素,甚至core掉。

即使是用const char*作key同样不安全,因为一旦const char*的生命期比hash_table短,那么hash_table中相应的key就已变为野指针。

验证:

不用char*作为hash_map的key-LMLPHP
 1 #include <iostream>
2 #include <ext/hash_map>
3 using namespace __gnu_cxx;
4 #include <function.h>
5 #include <cstring>
6 using namespace std;
7
8 struct mystrcmp
9 {
10 bool operator()(const char* s1, const char* s2)
11 {
12 return strcmp(s1, s2) == 0;
13 }
14 };
15
16 int main()
17 {
18 hash_map<char*, int, hash<char*>, mystrcmp> days;
19
20 days["Mon"] = 1;
21 days["Tue"] = 2;
22 cout << "now there is " << days.size() << " in hash_map" << endl;
23
24 days.clear();
25
26 char mon[8] = {0};
27 char tue[8] = {0};
28 strcpy(mon, "Mon");
29 strcpy(tue, "Tue");
30 days[mon] = 1;
31 days[tue] = 2;
32 cout << "now there is " << days.size() << " in hash_map" << endl;
33
34 char someday[8] = {0};
35 strcpy(someday, "Mon");
36 strcpy(mon, "Mon1");
37
38 cout << "now there is " << days.size() << " in hash_map" << endl;
39 cout << "Mon " << days[someday] << endl;
40 cout << "now there is " << days.size() << " in hash_map" << endl;
41 }
不用char*作为hash_map的key-LMLPHP

结论:

  • 不用char*或const char*作为hash_map的key。用string包装并代替它,同时为hash仿函数添一个string的特化版本
  • 一定要用char*的话,请用const char*,还要保证在hash_map的生命周期里,曾经insert过的const指针不要变成野指针
  • 尝试用unordered_map代替hash_map。首先它原生支持string,其次有效率优势,再次已经成为新标准,便于扩展。hash_map已经被放到backward里
 
 
 
标签: c++stlhash_map
05-11 11:23