不用char*作为hash

不用char*作为hash_map的key

尽量不用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的实现（省略了与讨论无关部分）：

 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 }

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指针）组成

工作过程是：

将key用_HashFn进行hash
将hash的结果执行取模操作%n（其中n是hashtable中bucket的数目），定位到具体bucket的位置
依次用_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就已变为野指针。

验证：

 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 }

now there is 2 in hash_map
now there is 2 in hash_map
now there is 2 in hash_map
Mon 0
now there is 3 in hash_map

结论：

不用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++, stl, hash_map