www.adminn.cn
站长正能量分享网!

php的hash算法介绍

AD:阿里云服务器企业会员更优惠 腾讯云香港,韩国免备案服务器1.8折优惠

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中的这个算法:

  1. static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength) 
  2.     register ulong hash = 5381; 
  3.  
  4.     /* variant with the hash unrolled eight times */ 
  5.     for (; nKeyLength >= 8; nKeyLength -=  { 
  6.         hash = ((hash << 5) + hash) + *arKey++; 
  7.         hash = ((hash << 5) + hash) + *arKey++; 
  8.         hash = ((hash << 5) + hash) + *arKey++; 
  9.         hash = ((hash << 5) + hash) + *arKey++; 
  10.         hash = ((hash << 5) + hash) + *arKey++; 
  11.         hash = ((hash << 5) + hash) + *arKey++; 
  12.         hash = ((hash << 5) + hash) + *arKey++; 
  13.         hash = ((hash << 5) + hash) + *arKey++; 
  14.     } 
  15.     switch (nKeyLength) { 
  16.         case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough… */ 
  17.         case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough… */ 
  18.         case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough… */ 
  19.         case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough… */ 
  20.         case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough… */ 
  21.         case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough… */ 
  22.         case 1: hash = ((hash << 5) + hash) + *arKey++; break
  23.         case 0: break
  24. EMPTY_SWITCH_DEFAULT_CASE() 
  25.     } 
  26.     return hash; 

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

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

在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

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

模板优惠价: (点击购买)
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《php的hash算法介绍》
文章链接:https://www.adminn.cn/news/8556.html
本站资源模板仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。2021.5月起,网站调整,暂不再分享免费模板。谢谢理解

Adminn.Cn 站长分享圈

帝国CMS精品模板腾讯云优惠券,代金券

本站源码仅供本地环境下学习借鉴研究使用!

源码请勿用于任何涉灰站点!净化网络,站长更有责!

支付宝扫一扫打赏