您当前的位置: 首页 > 网站编程 > PHP教程 > php的hash算法介绍

php的hash算法介绍

作者:不详 来源:网络 发布时间: 2014-08-08 16:37 点击:
PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法被广泛运用与多个软件项目,Apache, Perl和Berkeley DB等。对于字符串而言这是目前所知道的最好的哈希算法,原因在于该算法的速度非常快,而且分类非常好(冲突小,分布

php的hash算法介绍

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

  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 << 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

  看了这些, 我有理由相信这个初始值的选定能提供更好的分类.
分享到:
本文"php的hash算法介绍"由远航站长收集整理而来,仅供大家学习与参考使用。更多网站制作教程尽在远航站长站。
顶一下
(0)
0%
踩一下
(0)
0%
[点击 次] [返回上一页] [打印]
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 密码: 验证码:
关于本站 - 联系我们 - 网站声明 - 友情连接- 网站地图 - 站点地图 - 返回顶部
Copyright © 2007-2013 www.yhzhan.com(远航站长). All Rights Reserved .
远航站长:为中小站长提供最佳的学习与交流平台,提供网页制作与网站编程等各类网站制作教程.
官方QQ:445490277 网站群:26680406 网站备案号:豫ICP备07500620号-4