PHP哈希表實(shí)現(xiàn)算法原理解析

在PHP內(nèi)核中，其中一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)就是HashTable。我們常用的數(shù)組，在內(nèi)核中就是用HashTable來(lái)實(shí)現(xiàn)。那么，PHP的HashTable是怎么實(shí)現(xiàn)的呢？最近在看HashTable的數(shù)據(jù)結(jié)構(gòu)，但是算法書籍里面沒(méi)有具體的實(shí)現(xiàn)算法，剛好最近也在閱讀PHP的源碼，于是參考PHP的HashTable的實(shí)現(xiàn)，自己實(shí)現(xiàn)了一個(gè)簡(jiǎn)易版的HashTable，總結(jié)了一些心得，下面給大家分享一下。

HashTable的介紹

哈希表是實(shí)現(xiàn)字典操作的一種有效數(shù)據(jù)結(jié)構(gòu)。

定義

簡(jiǎn)單地說(shuō)，HashTable(哈希表)就是一種鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)。支持插入，查找，刪除等操作。在一些合理的假設(shè)下，在哈希表中的所有操作的時(shí)間復(fù)雜度是O(1)(對(duì)相關(guān)證明感興趣的可以自行查閱)。

實(shí)現(xiàn)哈希表的關(guān)鍵

在哈希表中，不是使用關(guān)鍵字做下標(biāo)，而是通過(guò)哈希函數(shù)計(jì)算出key的哈希值作為下標(biāo)，然后查找/刪除時(shí)再計(jì)算出key的哈希值，從而快速定位元素保存的位置。

在一個(gè)哈希表中，不同的關(guān)鍵字可能會(huì)計(jì)算得到相同的哈希值，這叫做“哈希沖突”，就是處理兩個(gè)或多個(gè)鍵的哈希值相同的情況。解決哈希沖突的方法有很多，開放尋址法，拉鏈法等等。

因此，實(shí)現(xiàn)一個(gè)好的哈希表的關(guān)鍵就是一個(gè)好的哈希函數(shù)和處理哈希沖突的方法。

Hash函數(shù)

判斷一個(gè)哈希算法的好壞有以下定義：

• 一致性，等價(jià)的鍵必然產(chǎn)生相等的哈希值；
  
• 高效性，計(jì)算簡(jiǎn)便；
  
• 均勻性，均勻地對(duì)所有的鍵進(jìn)行哈希。
  
• 哈希函數(shù)建立了關(guān)鍵值與哈希值的對(duì)應(yīng)關(guān)系，即：h = hash_func(key)。對(duì)應(yīng)關(guān)系見(jiàn)下圖：
  

hash-exam

設(shè)計(jì)一個(gè)完美的哈希函數(shù)就交由專家去做吧，我們只管用已有的較成熟的哈希函數(shù)就好了。PHP內(nèi)核使用的哈希函數(shù)是time33函數(shù)，又叫DJBX33A，其實(shí)現(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ù)使用了一個(gè)8次循環(huán)+switch來(lái)實(shí)現(xiàn)，是對(duì)for循環(huán)的優(yōu)化，減少循環(huán)的運(yùn)行次數(shù)，然后在switch里面執(zhí)行剩下的沒(méi)有遍歷到的元素。

拉鏈法

將所有具有相同哈希值的元素都保存在一條鏈表中的方法叫拉鏈法。查找的時(shí)候通過(guò)先計(jì)算key對(duì)應(yīng)的哈希值，然后根據(jù)哈希值找到對(duì)應(yīng)的鏈表，最后沿著鏈表順序查找相應(yīng)的值。

PHP的HashTable結(jié)構(gòu)

簡(jiǎn)單地介紹了哈希表的數(shù)據(jù)結(jié)構(gòu)之后，繼續(xù)看看PHP中是如何實(shí)現(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;

• nTableSize，HashTable的大小，以2的倍數(shù)增長(zhǎng)
• nTableMask，用在與哈希值做與運(yùn)算獲得該哈希值的索引取值，arBuckets初始化后永遠(yuǎn)是nTableSize-1
• nNumOfElements，HashTable當(dāng)前擁有的元素個(gè)數(shù)，count函數(shù)直接返回這個(gè)值
• nNextFreeElement，表示數(shù)字鍵值數(shù)組中下一個(gè)數(shù)字索引的位置
• pInternalPointer，內(nèi)部指針，指向當(dāng)前成員，用于遍歷元素
• pListHead，指向HashTable的第一個(gè)元素，也是數(shù)組的第一個(gè)元素
• pListTail，指向HashTable的最后一個(gè)元素，也是數(shù)組的最后一個(gè)元素。與上面的指針結(jié)合，在遍歷數(shù)組時(shí)非常方便，比如reset和endAPI
• arBuckets，包含bucket組成的雙向鏈表的數(shù)組，索引用key的哈希值和nTableMask做與運(yùn)算生成
• pDestructor，刪除哈希表中的元素使用的析構(gòu)函數(shù)
• persistent，標(biāo)識(shí)內(nèi)存分配函數(shù)，如果是TRUE，則使用操作系統(tǒng)本身的內(nèi)存分配函數(shù)，否則使用PHP的內(nèi)存分配函數(shù)
• nApplyCount，保存當(dāng)前bucket被遞歸訪問(wèn)的次數(shù)，防止多次遞歸
• bApplyProtection，標(biāo)識(shí)哈希表是否要使用遞歸保護(hù)，默認(rèn)是1，要使用

舉一個(gè)哈希與mask結(jié)合的例子：

例如，”foo”真正的哈希值（使用DJBX33A哈希函數(shù)）是193491849。如果我們現(xiàn)在有64容量的哈希表，我們明顯不能使用它作為數(shù)組的下標(biāo)。取而代之的是通過(guò)應(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;

• h，哈希值（或數(shù)字鍵值的key
• nKeyLength，key的長(zhǎng)度
• pData，指向數(shù)據(jù)的指針
• pDataPtr，指針數(shù)據(jù)
• pListNext，指向HashTable中的arBuckets鏈表中的下一個(gè)元素
• pListLast，指向HashTable中的arBuckets鏈表中的上一個(gè)元素
• pNext，指向具有相同hash值的bucket鏈表中的下一個(gè)元素
• pLast，指向具有相同hash值的bucket鏈表中的上一個(gè)元素
• arKey，key的名稱

PHP中的HashTable是采用了向量加雙向鏈表的實(shí)現(xiàn)方式，向量在arBuckets變量保存，向量包含多個(gè)bucket的指針，每個(gè)指針指向由多個(gè)bucket組成的雙向鏈表，新元素的加入使用前插法，即新元素總是在bucket的第一個(gè)位置。由上面可以看到，PHP的哈希表實(shí)現(xiàn)相當(dāng)復(fù)雜。這是它使用超靈活的數(shù)組類型要付出的代價(jià)。

HashTable相關(guān)API

• zend_hash_init
• zend_hash_add_or_update
• zend_hash_find
• zend_hash_del_key_or_index

zend_hash_init

函數(shù)執(zhí)行步驟

設(shè)置哈希表大小

設(shè)置結(jié)構(gòu)體其他成員變量的初始值 (包括釋放內(nèi)存用的析構(gòu)函數(shù)pDescructor)
詳細(xì)代碼注解點(diǎn)擊：zend_hash_init源碼

注：

1、pHashFunction在此處并沒(méi)有用到，php的哈希函數(shù)使用的是內(nèi)部的zend_inline_hash_func

2、zend_hash_init執(zhí)行之后并沒(méi)有真正地為arBuckets分配內(nèi)存和計(jì)算出nTableMask的大小，真正分配內(nèi)存和計(jì)算nTableMask是在插入元素時(shí)進(jìn)行CHECK_INIT檢查初始化時(shí)進(jìn)行。

zend_hash_add_or_update

函數(shù)執(zhí)行步驟

• 檢查鍵的長(zhǎng)度
• 檢查初始化
• 計(jì)算哈希值和下標(biāo)
• 遍歷哈希值所在的bucket，如果找到相同的key且值需要更新，則更新數(shù)據(jù)，否則繼續(xù)指向bucket的下一個(gè)元素，直到指向bucket的最后一個(gè)位置
• 為新加入的元素分配bucket，設(shè)置新的bucket的屬性值，然后添加到哈希表中

如果哈希表空間滿了，則重新調(diào)整哈希表的大小

zend_hash_add_or_update

CONNECT_TO_BUCKET_DLLIST是將新元素添加到具有相同hash值的bucket鏈表。

CONNECT_TO_GLOBAL_DLLIST是將新元素添加到HashTable的雙向鏈表。

詳細(xì)代碼和注解請(qǐng)點(diǎn)擊：zend_hash_add_or_update代碼注解。

zend_hash_find

函數(shù)執(zhí)行步驟

• 計(jì)算哈希值和下標(biāo)
• 遍歷哈希值所在的bucket，如果找到key所在的bucket，則返回值，否則，指向下一個(gè)bucket，直到指向bucket鏈表中的最后一個(gè)位置

詳細(xì)代碼和注解請(qǐng)點(diǎn)擊：zend_hash_find代碼注解。

zend_hash_del_key_or_index

函數(shù)執(zhí)行步驟

• 計(jì)算key的哈希值和下標(biāo)
• 遍歷哈希值所在的bucket，如果找到key所在的bucket，則進(jìn)行第三步，否則，指向下一個(gè)bucket，直到指向bucket鏈表中的最后一個(gè)位置
• 如果要?jiǎng)h除的是第一個(gè)元素，直接將arBucket[nIndex]指向第二個(gè)元素；其余的操作是將當(dāng)前指針的last的next執(zhí)行當(dāng)前的next
• 調(diào)整相關(guān)指針
• 釋放數(shù)據(jù)內(nèi)存和bucket結(jié)構(gòu)體內(nèi)存

詳細(xì)代碼和注解請(qǐng)點(diǎn)擊：zend_hash_del_key_or_index代碼注解。

性能分析

PHP的哈希表的優(yōu)點(diǎn)：PHP的HashTable為數(shù)組的操作提供了很大的方便，無(wú)論是數(shù)組的創(chuàng)建和新增元素或刪除元素等操作，哈希表都提供了很好的性能，但其不足在數(shù)據(jù)量大的時(shí)候比較明顯，從時(shí)間復(fù)雜度和空間復(fù)雜度看看其不足。

不足如下：

• 保存數(shù)據(jù)的結(jié)構(gòu)體zval需要單獨(dú)分配內(nèi)存，需要管理這個(gè)額外的內(nèi)存，每個(gè)zval占用了16bytes的內(nèi)存；
• 在新增bucket時(shí)，bucket也是額外分配，也需要16bytes的內(nèi)存；
• 為了能進(jìn)行順序遍歷，使用雙向鏈表連接整個(gè)HashTable，多出了很多的指針，每個(gè)指針也要16bytes的內(nèi)存；
• 在遍歷時(shí)，如果元素位于bucket鏈表的尾部，也需要遍歷完整個(gè)bucket鏈表才能找到所要查找的值
  

PHP的HashTable的不足主要是其雙向鏈表多出的指針及zval和bucket需要額外分配內(nèi)存，因此導(dǎo)致占用了很多內(nèi)存空間及查找時(shí)多出了不少時(shí)間的消耗。

后續(xù)

上面提到的不足，在PHP7中都很好地解決了，PHP7對(duì)內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)做了一個(gè)大改造，使得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, ' 個(gè)惡意的元素需要 ', $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, ' 個(gè)普通元素需要 ', $endTime - $startTime, ' 秒', "\n";

上面這個(gè)demo是有多個(gè)hash沖突時(shí)和無(wú)沖突時(shí)的時(shí)間消耗比較。筆者在PHP5.4下運(yùn)行這段代碼，結(jié)果如下

插入 65536 個(gè)惡意的元素需要 43.72204709053 秒

插入 65536 個(gè)普通元素需要 0.009843111038208 秒

而在PHP7上運(yùn)行的結(jié)果：

插入 65536 個(gè)惡意的元素需要 4.4028408527374 秒

插入 65536 個(gè)普通元素需要 0.0018510818481445 秒

可見(jiàn)不論在有沖突和無(wú)沖突的數(shù)組操作，PHP7的性能都提升了不少，當(dāng)然，有沖突的性能提升更為明顯。至于為什么PHP7的性能提高了這么多，值得繼續(xù)深究。

最后再安利一下，筆者github上有一個(gè)簡(jiǎn)易版的HashTable的實(shí)現(xiàn)：HashTable實(shí)現(xiàn)

另外，我在github有對(duì)PHP源碼更詳細(xì)的注解。感興趣的可以圍觀一下，給個(gè)star。PHP5.4源碼注解?？梢酝ㄟ^(guò)commit記錄查看已添加的注解。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。