php的hash算法介紹
Hash Table是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 -= {
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
看了這些, 我有理由相信這個初始值的選定能提供更好的分類.
相關(guān)文章
TP5(thinkPHP框架)實現(xiàn)后臺清除緩存功能示例
這篇文章主要介紹了TP5(thinkPHP框架)實現(xiàn)后臺清除緩存功能,結(jié)合實例形式分析了thinkPHP5結(jié)合layui插件實現(xiàn)后臺緩存清除相關(guān)的文件遍歷、刪除等操作技巧,需要的朋友可以參考下2019-05-05
這篇文章主要介紹了YII Framework的filter過濾器用法,結(jié)合實例形式分析了filter過濾器的功能,使用技巧與相關(guān)注意事項,需要的朋友可以參考下2016-03-03
這篇文章主要給大家介紹了關(guān)于如何利用PHP獲取漢字首字母并且分組排序的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用php具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-10-10
這篇文章主要介紹了Ubuntu下如何升級到PHP7.4的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
PHPMailer發(fā)送HTML內(nèi)容、帶附件的郵件實例
這篇文章主要介紹了PHPMailer發(fā)送HTML內(nèi)容、帶附件的郵件實例,發(fā)送的內(nèi)容包含圖片和文字,附件則發(fā)送的一個EXCEL表,需要的朋友可以參考下2014-07-07
tp5框架使用cookie加密算法實現(xiàn)登錄功能示例
這篇文章主要介紹了tp5框架使用cookie加密算法實現(xiàn)登錄功能,結(jié)合實例形式分析了thinkPHP5使用cookie加密算法的原理及登錄功能相關(guān)操作技巧,需要的朋友可以參考下2020-02-02
淺談Laravel POST,PUT,PATCH 路由的區(qū)別
今天小編就為大家分享一篇淺談Laravel POST,PUT,PATCH 路由的區(qū)別，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-10-10
如何通過View::first使用Laravel Blade的動態(tài)模板詳解
這篇文章主要給大家介紹了關(guān)于如何通過View::first使用Laravel Blade的動態(tài)模板的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用php具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起看看吧。2017-09-09
在Mac OS上編譯安裝Nginx+PHP+MariaDB開發(fā)環(huán)境的教程
這篇文章主要介紹了在Mac OS上編譯安裝Nginx+PHP+MariaDB開發(fā)環(huán)境的教程,包括使用phpize安裝PHP擴展的方法,需要的朋友可以參考下2016-02-02
此算法的解密方法是重新加密一次，便可還原，需要的朋友可以參考下2012-04-04