php的hash算法介绍_PHP教程-php教程-PHP中文网

php的hash算法介绍_PHP教程

php中文网

发布： 2016-07-13 10:37:31

原创

1140人浏览过

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 -= {
        hash = ((hash         hash = ((hash         hash = ((hash         hash = ((hash         hash = ((hash         hash = ((hash         hash = ((hash         hash = ((hash     }
    switch (nKeyLength) {
        case 7: hash = ((hash         case 6: hash = ((hash         case 5: hash = ((hash         case 4: hash = ((hash         case 3: hash = ((hash         case 2: hash = ((hash         case 1: hash = ((hash         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算法中, 我们可以看出很处细致的不同.