php hash算法实例分享

发布时间:2020-08-25编辑:脚本学堂
PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法被广泛运用与多个软件项目,Apache, Perl和Berkeley DB等。

Hash Table是PHP的核心,这话一点都不过分。
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 -=  {
        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的优化上也是煞费苦心

最后,hash的初始值设置成了5381, 相比在Apache中的times算法和Perl中的Hash算法(都采用初始hash为0), 为什么选5381呢?
5381的一些特性:
Magic Constant 5381:
1. odd number
2. prime number
3. deficient number
基于此,这个初始值的选定能提供更好的分类。