php的hash算法介绍_php实例_脚本之家

首先, 最不一样的就是, PHP中并没有使用直接乘33, 而是采用了:复制代码 代码如下:hash << 5 + hash

复制代码 代码如下:Magic Constant 5381:1.
odd number2. prime number3. deficient number看了这些,
我有理由相信这个初始值的选定能提供更好的分类.

在PHP的hash算法中, 我们可以看出很处细致的不同.

Hash Table是PHP的核心,这话一点都不过分。

算法的核心思想就是:复制代码 代码如下:hash
* 33 + str[i]

最后就是, hash的初始值设置成了5381,
相比在Apache中的times算法和Perl中的Hash算法, 为什么选5381呢?
具体的原因我也不知道, 但是我发现了5381的一些特性:

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

于此类似的思想, PHP鼓励8位一下的字符索引,
他以8为单位使用unrolled来提高效率,
这不得不说也是个很细节的,很细致的地方.

另外还有inline, register变量 …
可以看出PHP的开发者在hash的优化上也是煞费苦心

复制代码 代码如下:hashing function used
in Perl 5.005: # Return the hashed value of a string: $hash = perlhash
# (Defined by the PERL_HASH macro in hv.h) sub perlhash { $hash = 0;
foreach { $hash = $hash*33 + ord; } return $hash; }

在zend_hash.h中,我们可以找到在PHP中的这个算法:

然后, 特别要主意的就是使用的unrolled,
我前几天看过一片文章讲Discuz的缓存机制,
其中就有一条说是Discuz会根据帖子的热度不同采用不同的缓存策略,
根据用户习惯,而只缓存帖子的第一页.

复制代码 代码如下: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 = + *arKey++; hash = +
*arKey++; hash = + *arKey++; hash = + *arKey++; hash = + *arKey++;
hash = + *arKey++; hash = + *arKey++; hash = + *arKey++; } switch {
case 7: hash = + *arKey++; /* fallthrough… */ case 6: hash = +
*arKey++; /* fallthrough… */ case 5: hash = + *arKey++; /*
fallthrough… */ case 4: hash = + *arKey++; /* fallthrough… */
case 3: hash = + *php的hash算法介绍_php实例_脚本之家。arKey++; /* fallthrough… */ case 2: hash = +
*arKey++; /* fallthrough… */ case 1: hash = + *arKey++; break;
case 0: break;EMPTY_SWITCH_DEFAULT_CASE() } return hash;}

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

PHP的数组,关联数组,对象属性,函数表,符号表,等等都是用HashTable来做为容器的。

PHP的HashTable采用的拉链法来解决冲突, 这个自不用多说,
我今天主要关注的就是PHP的Hash算法, 和这个算法本身透露出来的一些思想。

这样当然会比用乘快了.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图