php的hash算法介绍(2)-木庄网络博客

相比在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

看了这些, 我有理由相信这个初始值的选定能提供更好的分类.

更多相关Discuz论坛的内容来自木庄网络博客