Hash Table是PHP的核心,这话一点都不过分.

PHP的数组,关联数组,对象属性,函数表,符号表,等等都是用HashTable来做为容器的.

PHP的HashTable采用的拉链法来解决冲突, 这个自不用多说, 我今天主要关注的就是PHP的Hash算法, 和这个算法本身透露出来的一些思想.

PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法被广泛运用与多个软件项目,Apache, Perl和Berkeley DB等. 对于字符串而言这是目前所知道的最好的哈希算法,原因在于该算法的速度非常快,而且分类非常好(冲突小,分布均匀).

算法的核心思想就是:

hash(i) = hash(i-1) * 33 + str[i]

在zend_hash.h中,我们可以找到在PHP中的这个算法:

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
   {
        register ulong hash = 5381;
 
        /* variant with the hash unrolled eight times */
       for (; nKeyLength >= 8; nKeyLength -= 8) {
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
           hash = ((hash << 5) + hash) + *arKey++;
           hash = ((hash << 5) + hash) + *arKey++;
           hash = ((hash << 5) + hash) + *arKey++;
           hash = ((hash << 5) + hash) + *arKey++;
           hash = ((hash << 5) + hash) + *arKey++;
       }
       switch (nKeyLength) {
           case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
           case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
           case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
           case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
           case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
           case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
           case 1: hash = ((hash << 5) + hash) + *arKey++; break;
           case 0: break;
   EMPTY_SWITCH_DEFAULT_CASE()
       }
       return hash;
   }

相比在Apache和Perl中直接采用的经典Times 33算法:

hashing function used in Perl 5.005:
      # Return the hashed value of a string: $hash = perlhash("key")
     # (Defined by the PERL_HASH macro in hv.h)
      sub perlhash
      {
         $hash = 0;
        foreach (split //, shift) {
              $hash = $hash*33 + ord($_);
         }
        return $hash;
    }

在PHP的hash算法中, 我们可以看出很处细致的不同.

首先, 最不一样的就是, PHP中并没有使用直接乘33, 而是采用了:

hash << 5 + hash

这样当然会比用乘快了.

然后, 特别要主意的就是使用的unrolled, 我前几天看过一片文章讲Discuz的缓存机制, 其中就有一条说是Discuz会根据帖子的热度不同采用不同的缓存策略, 根据用户习惯,而只缓存帖子的第一页(因为很少有人会翻帖子).

于此类似的思想, PHP鼓励8位一下的字符索引, 他以8为单位使用unrolled来提高效率, 这不得不说也是个很细节的,很细致的地方.

另外还有inline, register变量 … 可以看出PHP的开发者在hash的优化上也是煞费苦心

本文地址:http://www.yaronspace.cn/blog/index.php/archives/604

来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/604