现在的位置: 首页 > 综合 > 正文

思考:如何提高字符串为键的哈希表的性

2014年12月05日 ⁄ 综合 ⁄ 共 2404字 ⁄ 字号 评论关闭
引发这个思考是因为今天在网上看见一个叫做MurmurHash2的词,还有一个叫做DJB的词。我这人就一坏毛病,一看见稀奇古怪的闻所未闻的东东,就好像饿慌了的狗看见肉骨头。于是,从下午17点一直看到22点,了解了很多关于HASH的知识。
MurmurHash2和DJB都是一种将字符串转换成整型值的HASH函数算法,这里(http://blog.csdn.net/wwwsq/archive/2009/06/09/4254123.aspx)的文章介绍了MurmurHash2算法和DJB算法的性能差异,及其使用建议。
目前我所了解的字符串转换成整形的字符串哈希函数是STL中的,代码如下:
//ext/hash_fun.h
inline size_t
__stl_hash_string(const char* __s)
{
unsigned long __h = 0;
for ( ; *__s; ++__s)
__h = 5*__h + *__s;
return size_t(__h);
}

由上可见,STL中的字符串HASH算法是一个时间复杂度为O(N)的算法,实现原理为循环乘5加ASCII码。
相关的字符串HASH算法的文章还有:
字符串hash算法比较: http://blog.chinaunix.net/u1/38279/showart_447862.html
大量Hash算法的实现: http://hi.baidu.com/algorithms/blog/item/79caabee879ece2a2cf53440.html
哈希算法(Hash Algorithm)初探: http://blog.csdn.net/wwwsq/archive/2007/03/12/1526595.aspx
General Purpose Hash Function Algorithms: http://www.partow.net/programming/hashfunctions/

恕我愚昧,我个人认为字符串HASH函数的好坏在于产生的HASH CODE的冲突的大小,比如,对100亿海量字符串进行HASH CODE的运算,平均冲突最小的HASH函数就是最好的。而在性能方面,HASH函数的时间复杂度应该都是与字符串长度相关的,也就是O(N)。仔细看了一下MurmurHash2的算法实现,在预先计算字符串长度的前提下,以整数类型计算HASH而不是char类型来计算,对于长字符串,HASH函数的性能提高应该还是比较明显的。但对于其他的一些HASH函数的实现,我实在无法区分其优劣。

另外看了两篇关于HASH函数和HASH表的性能优化的文章:
Cuckoo hash算法介绍: http://hi.baidu.com/algorithms/blog/item/eb89b582add48f95f703a61e.html
(对同一字符串计算两个HASH值来优化性能)
打造最快的Hash表: http://www.yuanma.org/data/2006/1104/article_1774.htm
(介绍了暴雪提供的一种HASH算法,对同一字符串计算三个HASH值来代替发生冲突的时候所进行的字符串比较)

上面两篇文章的思想可以借鉴,但是我认为这并不能提高字符串为键的哈希表的性能,因为HASH函数的时间复杂度为O(N),虽然在查找和比较上节约了时间,但是在计算HASH值上又增加了成本。

在高性能的服务器环境,我觉得可以从以下角度提高字符串为键的HASH表的性能:
1、使用经过验证的冲突小的HASH函数;
当然,我不知道这个函数是什么,但相信它一定存在。
2、使用性能高的字符串HASH函数;
比如MurmurHash2和DJB两种算法,传说性能就很高。
3、预先计算HASH值,避免每次按照字符串搜索的时候都去执行HASH函数;
关于这个技巧,请参考我之前写的一篇文章:《ext/hash_map:进一步提高字符串为键的哈希表的性能》(http://hi.baidu.com/ah%5F%5Ffu/blog/item/fb9b0c2423786b094d088df3.html)
4、在第三点经验的基础上,通过不同的函数预先计算两个HASH值,在发生冲突的时候使用第二个HASH函数进行比较;
当然,也要考虑多计算一个HASH值的初始化成本。
5、用字符串长度比较和内存比较来代替字符串比较;
这也是预先计算的思想,预先计算出字符串的长度,HASH键的比较函数大概是这样:
struct NodeCompare
{
bool operator()(const HashNode* lsh, const HashNode* rsh) const
{
return lsh->HashCode == rsh->HashCode && //在HASH CODE冲突的时候继续比较
lsh->KeyLength == rsh->KeyLength && //因为两个不同的字符串可能产生同样的HASH值
0==memcmp(lsh->Key, rsh->Key, lsh->KeyLength); //所以在发生HASH冲突的时候一定要比较内容
}
};
以上的代码中,先比较长度,在长度相同的情况下,用内存比较函数来比较内容。
6、使用并行的HASH表实现;
在服务器环境,往往不是一个线程来操作HASH表,因此可以选用intel tbb库提供的concurrent_hash_map。INTEL实现的这个并行HASH容器在每个HASH节点上额外存储了一个读写自旋锁,在多线程并发访问的情况下能大大提高性能。
关于tbb::concurrent_hash_map的研究,请看我写的另一篇文章:《tbb::concurrent_hash_map源码分析》(http://hi.baidu.com/ah%5F%5Ffu/blog/item/30946294c2aed116d31b7045.html)

抱歉!评论已关闭.