Times33算法与最快的Hash表(汇聚版本)–php开发者是程序高手

关于times33算法

不约而同的,几乎所有的流行的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的对话)》一文里,讲述blizzard如何改良hash表的。在上述哈希算法里面有一段 “seed2 + (seed2 << 5)” 相当于乘以33,其实可以看作是times33算法的变种。我对blizzard这种实现方法的效率存有怀疑。

上述blizzard的哈希算法的核心如下(我给cryptTable赋了最简单的值,而且把dwHashType设为了1):

01 inline UINT CMyMap::HashKey(LPCTSTR key) const
02 {
03     int dwHashType = 1;
04     unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
05     int ch;
06     while(*key != 0)
07     {
08         ch = toupper(*key++);
09         
10         //seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
11         seed1 = ((dwHashType << 8) + ch) ^ (seed1 + seed2);
12         seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
13     }
14     return seed1;
15 }

我进行了一下测试,发现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算法如下:

1 inline UINT CMyMap::HashKey(LPCTSTR key) const
2 {
3     UINT nHash = 0;
4     while (*key)
5         nHash = (nHash << 5) + nHash + *key++;
6     return nHash;
7 }

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

我的理解是:这是为了让同一个字符串,可以根据 dwHashType 的不同而计算出不同的独立的hash值。为了实现这个目的,blizzard的这个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,不过这次似乎有人夸暴雪夸错方向了:)

 

php, apache, perl, bsddb都使用time33哈希.

最简单的版本

    uint32_t time33(char const *str, int len)
{
unsigned long  hash = 0;
for (int i = 0; i < len; i++) {
hash = hash *33 + (unsigned long) str[i];
}
return hash;
}

这个版本最可以体现time33的算法思路,够简单。

 

把乘法操作换成位操作

unsigned long time33(char const *str, int len)
{
unsigned long  hash = 0;
for (int i = 0; i < len; i++) {
hash = ((hash <<5) + hash) + (unsigned long) str[i];
}
return hash;
}

59个字符1000 0000次运行(gcc没有开启优化,因为开了优化后两个函数的实际代码会一样)

第一个:

real    0m4.389s
user    0m4.388s
sys     0m0.000s

第二个:

real    0m4.137s
user    0m4.120s
sys     0m0.000s

gcc –O2优化后是

real    0m1.367s
user    0m1.360s
sys     0m0.000s

 

php版本

inline unsigned time33(char const*str, int len)
{
unsigned long hash = 5381;
/* variant with the hash unrolled eight times */
for (; len >= 8; len -= 8) {
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
}
switch (len) {
case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough… */
case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough… */
case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough… */
case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough… */
case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough… */
case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough… */
case 1: hash = ((hash << 5) + hash) + *str++; break;
case 0: break;
}
return hash;
}

59个字符,1000 0000次

real    0m1.088s
user    0m1.068s
sys     0m0.000s

速度提升主要在循环展开, 对于短字符,这个是不明显的。

php版本的hash初始值是5381, 这个

Magic Constant 5381:

  1. odd number

2. prime number

3. deficient number

4. 001/010/100/000/101 b

Apache版本

unsigned long time33(char const  *str, int *len)
{
unsigned long hash = 0;

const char *p=str;
if (*len<=0) {
for(p = str; *p; p++) {
hash = hash * 33 + *p;
}
*len = p – str;
}
else {
int i = *len;
for (p = str;i; i–, p++) {
hash = hash * 33 + *p;
}
}
return hash;
}

测试结果

real    0m1.418s
user    0m1.412s
sys     0m0.004s

 

综上,我的改进版本

#define likely(x) __builtin_expect((x),1)
#define unlikely(x) __builtin_expect((x),0)
//php版本
unsigned long time33(char const *str, int len=-1)
{
unsigned long hash = 5381;
/* variant with the hash unrolled eight times */
char const *p = str;
if (unlikely(len<0)) {
for(; *p; p++) {
hash = hash * 33 + *p;
}
return hash;
}

#define TIME33_HASH_MIXED_CH()  hash = ((hash<<5)+hash) + *p++
for (; len >= 8; len -= 8) {
TIME33_HASH_MIXED_CH(); //1
TIME33_HASH_MIXED_CH(); //2
TIME33_HASH_MIXED_CH(); //3
TIME33_HASH_MIXED_CH(); //4
TIME33_HASH_MIXED_CH(); //5
TIME33_HASH_MIXED_CH(); //6
TIME33_HASH_MIXED_CH(); //7
TIME33_HASH_MIXED_CH(); //8
}
switch (len) {
case 7: TIME33_HASH_MIXED_CH(); /* fallthrough… */
case 6: TIME33_HASH_MIXED_CH(); /* fallthrough… */
case 5: TIME33_HASH_MIXED_CH(); /* fallthrough… */
case 4: TIME33_HASH_MIXED_CH(); /* fallthrough… */
case 3: TIME33_HASH_MIXED_CH(); /* fallthrough… */
case 2: TIME33_HASH_MIXED_CH(); /* fallthrough… */
case 1: TIME33_HASH_MIXED_CH(); break;
case 0: break;
}
return hash;
}

#undef TIME33_HASH_MIXED_CH

测试结果

real    0m1.072s
user    0m1.064s
sys     0m0.000s

测试过, 重复率在 1/2000。

 

为什么是33的倍数, PHP中注释是

  • DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
  •   This is Daniel J. Bernstein’s popular `times 33′ hash function as
  •   posted by him years ago on comp.lang.c. It basically uses a function
  •   like “hash(i) = hash(i-1) * 33 + str[i]”. This is one of the best
  •   known hash functions for strings. Because it is both computed very
  •   fast and distributes very well.
  •   The magic of number 33, i.e. why it works better than many other
  •   constants, prime or not, has never been adequately explained by
  •   anyone. So I try an explanation: if one experimentally tests all
  •   multipliers between 1 and 256 (as RSE did now) one detects that even
  •   numbers are not useable at all. The remaining 128 odd numbers
  •   (except for the number 1) work more or less all equally well. They
  •   all distribute in an acceptable way and this way fill a hash table
  •   with an average percent of approx. 86%.
  •   If one compares the Chi^2 values of the variants, the number 33 not
  •   even has the best value. But the number 33 and a few other equally
  •   good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
  •   advantage to the remaining numbers in the large set of possible
  •   multipliers: their multiply operation can be replaced by a faster
  •   operation based on just one shift plus either a single addition
  •   or subtraction operation. And because a hash function has to both
  •   distribute good _and_ has to be very fast to compute, those few
  •   numbers should be preferred and seems to be the reason why Daniel J.
  •   Bernstein also preferred it.
  •                    — Ralf S. Engelschall rse@engelschall.com

其它倍数

Ngix使用的是 time31

Tokyo Cabinet使用的是 time37

Bob在他的文章说,小写英文词汇适合33, 大小写混合使用65。time33比较适合的是英文词汇的hash.

 

 

阿海兄弟,哎,愿你一路走好!

未经允许不得转载:智慧,启迪人生 » Times33算法与最快的Hash表(汇聚版本)–php开发者是程序高手

赞 (0) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏