HashTable是PHP的核心，這話一點都不過分。PHP的數(shù)組、關(guān)聯(lián)數(shù)組、對象屬性、函數(shù)表、符號表等等都是用HashTable來做為容器的。

PHP的HashTable采用的拉鏈法來解決沖突，這個自不用多說，我今天主要關(guān)注的就是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 -= 8) {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中直接采用的經(jīng)典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算法中，我們可以看出很處細(xì)致的不同。首先，最不一樣的就是，PHP中并沒有使用直接乘33，而是采用了：

hash << 5 + hash

這樣當(dāng)然會比用乘快了。

然后，特別要主意的就是使用的unrolled，我前幾天看過一篇文章講Discuz的緩存機制，其中就有一條說是Discuz會根據(jù)帖子的熱度不同采用不同的緩存策略，根據(jù)用戶習(xí)慣，而只緩存帖子的第一頁(因為很少有人會翻帖子)。

于此類似的思想，PHP鼓勵8位一下的字符索引，他以8為單位使用unrolled來提高效率，這不得不說也是個很細(xì)節(jié)的，很細(xì)致的地方。

另外還有inline，register變量 … 可以看出PHP的開發(fā)者在hash的優(yōu)化上也是煞費苦心。

最后就是，hash的初始值設(shè)置成了5381，相比在Apache中的times算法和Perl中的Hash算法(都采用初始hash為0)，為什么選5381呢？具體的原因我也不知道，但是我發(fā)現(xiàn)了5381的一些特性：

Magic Constant 5381: 1. odd number 2. prime number 3. deficient number 4. 001/010/100/000/101 b

看了這些，我有理由相信這個初始值的選定能提供更好的分類。

至于說，為什么是Times 33而不是Times 其他數(shù)字，在PHP Hash算法的注釋中也有一些說明，希望對有興趣的同學(xué)有用：

DJBX33A (Daniel J. Bernstein, Times 33 with Addition)This is Daniel J. Bernstein’s popular `times 33’ hash function asposted by him years ago on comp.lang.c. It basically uses a functionlike ``hash(i) = hash(i-1) * 33 + str[i]’’. This is one of the bestknown hash functions for strings. Because it is both computed veryfast and distributes very well.The magic of number 33, i.e. why it works better than many otherconstants, prime or not, has never been adequately explained byanyone. So I try an explanation: if one experimentally tests allmultipliers between 1 and 256 (as RSE did now) one detects that evennumbers are not useable at all. The remaining 128 odd numbers(except for the number 1) work more or less all equally well. Theyall distribute in an acceptable way and this way fill a hash tablewith an average percent of approx. 86%.If one compares the Chi^2 values of the variants, the number 33 noteven has the best value. But the number 33 and a few other equallygood numbers like 17, 31, 63, 127 and 129 have nevertheless a greatadvantage to the remaining numbers in the large set of possiblemultipliers: their multiply operation can be replaced by a fasteroperation based on just one shift plus either a single additionor subtraction operation. And because a hash function has to bothdistribute good _and_ has to be very fast to compute, those fewnumbers should be preferred and seems to be the reason why Daniel J.Bernstein also preferred it. -- Ralf S. Engelschall <[email protected]>