哈希算法(Hash Algorithm)初探[转载]

不约而同的，几乎所有的流行的hash map都采用了DJB hash function，俗称“Times33”算法。

Perl、Berkeley DB 、Apache、MFC、STL 等等。

times33的算法也很简单，就是不断的乘33。nHash = nHash*33 + *key++;

我没找到什么理论可以说明这种算法的合理性，据说只是通过测试和实践发现这个算法是比较好的。如果有哪位能够提供这方面的资料，不胜感激。

我把times33和一些其他哈希算法做过比较，times33确实比我找到的其他哈希算法都更快。另外，有人说times33对英文字母效率比较好，处理中文的时候效率就比较低；我对此进行了一些测试，发现times33在处理ascii和中文的时候，性能差异在千分之三以下，我认为这是正常的误差。



《打造最快的Hash表(和Blizzard的对话)》http://blog.csdn.net/zeronecpp/archive/2005/04/11/342756.aspx
这是在别人的blog上看到的一篇文章，讲述blizzard如何改良hash表的。在上述哈希算法里面有一段 “seed2 + (seed2 << 5)” 相当于乘以33，其实可以看作是times33算法的变种。我对blizzard这种实现方法的效率存有怀疑。

上述blizzard的哈希算法的核心如下（我给cryptTable赋了最简单的值，而且把dwHashType设为了1）：

inline UINT CMyMap::HashKey(LPCTSTR key) const
{
    int dwHashType = 1;
    unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
    int ch;
    while(*key != 0)
    { 
        ch = toupper(*key++);
        
        //seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
        seed1 = ((dwHashType << 8) + ch) ^ (seed1 + seed2);
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 
    }
    return seed1; 
}

 
我进行了一下测试，发现blizzard的哈希算法，分布不如经典的times33算法。它的分布如下：elements=10000, good=4293 bad2=1786 bad3=528 bad4=109 vbad=22
而经典times33算法的分布是：elements=10000, good=4443 bad2=1775 bad3=501 bad4=107 vbad=15
说明：这是我测试程序的输出，测试的时候，我通过InitHashTable()把bucket个数设为了12007。输出中的elements表示哈希表中一共存放了多少个元素，good表示“只有一个元素”的bucket个数，bad2表示“有两个元素”的bucket个数，bad3表示“有三个元素”的bucket个数，vbad表示“有五个或者五个以上元素”的bucket个数。

经典times33算法如下：

inline UINT CMyMap::HashKey(LPCTSTR key) const
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

 
从代码可以很明显的看出，blizzard的这个hash算法的计算工作量也要比经典的times33算法大很多。

我的理解是：这是为了让让同一个字符串，可以根据dwHashType 的不同而计算出不同的独立的hash值。为了实现这个目的，blizzard的这个hash算法在性能上已经付出了一些代价。

//
// 以上是对hash算法的比较
/////////////////////////////////////////
// 以下是对hash表整体结构的比较
//

另外，blizzard这个算法本质上还是把数据放在hash bucket里面，也同样是在每个hash bucket里面有一个list队列。
只不过一般的hash表，在找到hash bucket之后，就逐个的直接比较element；而blizzard的这个hash表，则是用“额外的两个hash值的比较”来代替element的直接比较。孰优孰劣要看具体的应用环境。
考虑到计算三次hash值的工作量，我觉得如果设置一个合适的hash bucket count，blizzard的做法可能还要更慢。
上面我做的hash分布测试已经表明，当hash bucket count比elements大20%以上的时候，查找一个element的strcmp调用次数大约是(4443*1+1175*2*1.5+501*3*2+107*4*2.5+15*5*3)/10000=1.2269次，大约是1.2次。（4443个bucket只有一个element，因此一次strcmp就可以确认了。有1175个bucket有两个元素，平均要1.5次strcmp才能找到它。以此类推。）
做1.2次strcmp()和做2次HashKey()相信大家都知道谁比较耗时了。


看来，这个所谓”最快的hash表“似乎有点名不副实呢？还是另有玄机我没看透？
所谓"One-way hash"其实就是不可逆hash，主要是用来加密用的，和速度快不快没什么关系。实际上"One-way hash"为了达到不可逆的目的，通常总是要更慢一些。blizzard是我很喜欢的公司，我也是暴雪的铁杆fans，不过这次似乎有人夸暴雪夸错方向了:)

在google上搜索“hash Algorithm”可以搜到很多有趣的东西。
http://www.partow.net/programming/hashfunctions/ 是一篇很有趣的文章。