php的hash算法介绍
|
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 看了这些,我有理由相信这个初始值的选定能提供更好的分类. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |