在PHP內(nèi)核中，其中一個很重要的數(shù)據(jù)結(jié)構(gòu)就是HashTable。我們常用的數(shù)組，在內(nèi)核中就是用HashTable來實現(xiàn)。那么，PHP的HashTable是怎么實現(xiàn)的呢？最近在看HashTable的數(shù)據(jù)結(jié)構(gòu)，但是算法書籍里面沒有具體的實現(xiàn)算法，剛好最近也在閱讀PHP的源碼，于是參考PHP的HashTable的實現(xiàn)，自己實現(xiàn)了一個簡易版的HashTable，總結(jié)了一些心得，下面給大家分享一下。
HashTable的介紹
哈希表是實現(xiàn)字典操作的一種有效數(shù)據(jù)結(jié)構(gòu)。
定義
簡單地說，HashTable(哈希表)就是一種鍵值對的數(shù)據(jù)結(jié)構(gòu)。支持插入，查找，刪除等操作。在一些合理的假設(shè)下，在哈希表中的所有操作的時間復(fù)雜度是O(1)(對相關(guān)證明感興趣的可以自行查閱)。
實現(xiàn)哈希表的關(guān)鍵
在哈希表中，不是使用關(guān)鍵字做下標(biāo)，而是通過哈希函數(shù)計算出key的哈希值作為下標(biāo)，然后查找/刪除時再計算出key的哈希值，從而快速定位元素保存的位置。
在一個哈希表中，不同的關(guān)鍵字可能會計算得到相同的哈希值，這叫做“哈希沖突”，就是處理兩個或多個鍵的哈希值相同的情況。解決哈希沖突的方法有很多，開放尋址法，拉鏈法等等。
因此，實現(xiàn)一個好的哈希表的關(guān)鍵就是一個好的哈希函數(shù)和處理哈希沖突的方法。
Hash函數(shù)
判斷一個哈希算法的好壞有以下定義：
hash-exam
設(shè)計一個完美的哈希函數(shù)就交由專家去做吧，我們只管用已有的較成熟的哈希函數(shù)就好了。PHP內(nèi)核使用的哈希函數(shù)是time33函數(shù)，又叫DJBX33A，其實現(xiàn)如下：
static inline ulong zend_inline_hash_func(const 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;
}
注：函數(shù)使用了一個8次循環(huán)+switch來實現(xiàn)，是對for循環(huán)的優(yōu)化，減少循環(huán)的運行次數(shù)，然后在switch里面執(zhí)行剩下的沒有遍歷到的元素。
拉鏈法
將所有具有相同哈希值的元素都保存在一條鏈表中的方法叫拉鏈法。查找的時候通過先計算key對應(yīng)的哈希值，然后根據(jù)哈希值找到對應(yīng)的鏈表，最后沿著鏈表順序查找相應(yīng)的值。
PHP的HashTable結(jié)構(gòu)
簡單地介紹了哈希表的數(shù)據(jù)結(jié)構(gòu)之后，繼續(xù)看看PHP中是如何實現(xiàn)哈希表的。
PHP內(nèi)核hashtable的定義：
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
舉一個哈希與mask結(jié)合的例子：
例如，”foo”真正的哈希值（使用DJBX33A哈希函數(shù)）是193491849。如果我們現(xiàn)在有64容量的哈希表，我們明顯不能使用它作為數(shù)組的下標(biāo)。取而代之的是通過應(yīng)用哈希表的mask，然后只取哈希表的低位。
hash | 193491849 | 0b1011100010000111001110001001 mask | 63 | 0b0000000000000000000000111111 ---------------------------------------------------------------------- = index | = 9 | = 0b0000000000000000000000001001
因此，在哈希表中，foo是保存在arBuckets中下標(biāo)為9的bucket向量中。
bucket結(jié)構(gòu)體的定義
typedef struct bucket {
ulong h;
uint nKeyLength;
void *pData;
void *pDataPtr;
struct bucket *pListNext;
struct bucket *pListLast;
struct bucket *pNext;
struct bucket *pLast;
const char *arKey;
} Bucket;
PHP中的HashTable是采用了向量加雙向鏈表的實現(xiàn)方式，向量在arBuckets變量保存，向量包含多個bucket的指針，每個指針指向由多個bucket組成的雙向鏈表，新元素的加入使用前插法，即新元素總是在bucket的第一個位置。由上面可以看到，PHP的哈希表實現(xiàn)相當(dāng)復(fù)雜。這是它使用超靈活的數(shù)組類型要付出的代價。
HashTable相關(guān)API
zend_hash_init
函數(shù)執(zhí)行步驟
設(shè)置哈希表大小
設(shè)置結(jié)構(gòu)體其他成員變量的初始值 (包括釋放內(nèi)存用的析構(gòu)函數(shù)pDescructor)
詳細(xì)代碼注解點擊：zend_hash_init源碼
注：
1、pHashFunction在此處并沒有用到，php的哈希函數(shù)使用的是內(nèi)部的zend_inline_hash_func
2、zend_hash_init執(zhí)行之后并沒有真正地為arBuckets分配內(nèi)存和計算出nTableMask的大小，真正分配內(nèi)存和計算nTableMask是在插入元素時進(jìn)行CHECK_INIT檢查初始化時進(jìn)行。
zend_hash_add_or_update
函數(shù)執(zhí)行步驟
如果哈希表空間滿了，則重新調(diào)整哈希表的大小
zend_hash_add_or_update
CONNECT_TO_BUCKET_DLLIST是將新元素添加到具有相同hash值的bucket鏈表。
CONNECT_TO_GLOBAL_DLLIST是將新元素添加到HashTable的雙向鏈表。
詳細(xì)代碼和注解請點擊：zend_hash_add_or_update代碼注解。
zend_hash_find
函數(shù)執(zhí)行步驟
詳細(xì)代碼和注解請點擊：zend_hash_find代碼注解。
zend_hash_del_key_or_index
函數(shù)執(zhí)行步驟
詳細(xì)代碼和注解請點擊：zend_hash_del_key_or_index代碼注解。
性能分析
PHP的哈希表的優(yōu)點：PHP的HashTable為數(shù)組的操作提供了很大的方便，無論是數(shù)組的創(chuàng)建和新增元素或刪除元素等操作，哈希表都提供了很好的性能，但其不足在數(shù)據(jù)量大的時候比較明顯，從時間復(fù)雜度和空間復(fù)雜度看看其不足。
不足如下：
PHP的HashTable的不足主要是其雙向鏈表多出的指針及zval和bucket需要額外分配內(nèi)存，因此導(dǎo)致占用了很多內(nèi)存空間及查找時多出了不少時間的消耗。
后續(xù)
上面提到的不足，在PHP7中都很好地解決了，PHP7對內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)做了一個大改造，使得PHP的效率高了很多，因此，推薦PHP開發(fā)者都將開發(fā)和部署版本更新吧。看看下面這段PHP代碼：
?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key = $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 個惡意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key = $maxKey; ++$key) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 個普通元素需要 ', $endTime - $startTime, ' 秒', "\n";
上面這個demo是有多個hash沖突時和無沖突時的時間消耗比較。筆者在PHP5.4下運行這段代碼，結(jié)果如下
插入 65536 個惡意的元素需要 43.72204709053 秒
插入 65536 個普通元素需要 0.009843111038208 秒
而在PHP7上運行的結(jié)果：
插入 65536 個惡意的元素需要 4.4028408527374 秒
插入 65536 個普通元素需要 0.0018510818481445 秒
可見不論在有沖突和無沖突的數(shù)組操作，PHP7的性能都提升了不少，當(dāng)然，有沖突的性能提升更為明顯。至于為什么PHP7的性能提高了這么多，值得繼續(xù)深究。
最后再安利一下，筆者github上有一個簡易版的HashTable的實現(xiàn)：HashTable實現(xiàn)
另外，我在github有對PHP源碼更詳細(xì)的注解。感興趣的可以圍觀一下，給個star。PHP5.4源碼注解。可以通過commit記錄查看已添加的注解。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
標(biāo)簽：哈密 池州 阿里 孝感 那曲 濟源 北京 日照
巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《PHP哈希表實現(xiàn)算法原理解析》，本文關(guān)鍵詞 PHP,哈希,表,實現(xiàn),算法,原理,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請?zhí)峁┫嚓P(guān)信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。
