[PHP核心探索]PHP中的哈希表

在PHP核心中，其中一個很重要的資料結構就是HashTable。我們常用的數組，在核心中就是用HashTable來實作。那麼，PHP的HashTable是怎麼實作的呢？最近在看HashTable的資料結構，但是算法書籍裡面沒有具體的實作算法，剛好最近也在閱讀PHP的源碼，于是參考PHP的HashTable的實作，自己實作了一個簡易版的HashTable，總結了一些心得，下面給大家分享一下。

筆者github上有一個簡易版的HashTable的實作：HashTable實作

另外，我在github有對PHP源碼更詳細的注解。感興趣的可以圍觀一下，給個star。PHP5.4源碼注解。可以通過commit記錄檢視已添加的注解。

哈希表是實作字典操作的一種有效資料結構。

簡單地說，HashTable(哈希表)就是一種鍵值對的資料結構。支援插入，查找，删除等操作。在一些合理的假設下，在哈希表中的所有操作的時間複雜度是O(1)(對相關證明感興趣的可以自行查閱)。

在哈希表中，不是使用關鍵字做下标，而是通過哈希函數計算出key的哈希值作為下标，然後查找/删除時再計算出key的哈希值，進而快速定位元素儲存的位置。

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

是以，實作一個好的哈希表的關鍵就是一個好的哈希函數和處理哈希沖突的方法。

判斷一個雜湊演算法的好壞有以下四個定義：

一緻性，等價的鍵必然産生相等的哈希值； 高效性，計算簡便； 均勻性，均勻地對所有的鍵進行哈希。

哈希函數建立了關鍵值與哈希值的對應關系，即：h = hash_func(key)。對應關系見下圖：

設計一個完美的哈希函數就交由專家去做吧，我們隻管用已有的較成熟的哈希函數就好了。PHP核心使用的哈希函數是time33函數，又叫DJBX33A，其實作如下：

注：函數使用了一個8次循環+switch來實作，是對for循環的優化，減少循環的運作次數，然後在switch裡面執行剩下的沒有周遊到的元素。

将所有具有相同哈希值的元素都儲存在一條連結清單中的方法叫拉鍊法。查找的時候通過先計算key對應的哈希值，然後根據哈希值找到對應的連結清單，最後沿着連結清單順序查找相應的值。

具體儲存後的結構圖如下：

簡單地介紹了哈希表的資料結構之後，繼續看看PHP中是如何實作哈希表的。

nTableSize，HashTable的大小，以2的倍數增長 nTableMask，用在與哈希值做與運算獲得該哈希值的索引取值，arBuckets初始化後永遠是nTableSize-1 nNumOfElements，HashTable目前擁有的元素個數，count函數直接傳回這個值 nNextFreeElement，表示數字鍵值數組中下一個數字索引的位置 pInternalPointer，内部指針，指向目前成員，用于周遊元素 pListHead，指向HashTable的第一個元素，也是數組的第一個元素 pListTail，指向HashTable的最後一個元素，也是數組的最後一個元素。與上面的指針結合，在周遊數組時非常友善，比如reset和endAPI arBuckets，包含bucket組成的雙向連結清單的數組，索引用key的哈希值和nTableMask做與運算生成 pDestructor，删除哈希表中的元素使用的析構函數 persistent，辨別記憶體配置設定函數，如果是TRUE，則使用作業系統本身的記憶體配置設定函數，否則使用PHP的記憶體配置設定函數 nApplyCount，儲存目前bucket被遞歸通路的次數，防止多次遞歸 bApplyProtection，辨別哈希表是否要使用遞歸保護，預設是1，要使用

舉一個哈希與mask結合的例子：

例如，”foo”真正的哈希值（使用DJBX33A哈希函數）是193491849。如果我們現在有64容量的哈希表，我們明顯不能使用它作為數組的下标。取而代之的是通過應用哈希表的mask，然後隻取哈希表的低位。

是以，在哈希表中，foo是儲存在arBuckets中下标為9的bucket向量中。

h，哈希值（或數字鍵值的key nKeyLength，key的長度 pData，指向資料的指針 pDataPtr，指針資料 pListNext，指向HashTable中的arBuckets連結清單中的下一個元素 pListLast，指向HashTable中的arBuckets連結清單中的上一個元素 pNext，指向具有相同hash值的bucket連結清單中的下一個元素 pLast，指向具有相同hash值的bucket連結清單中的上一個元素 arKey，key的名稱

PHP中的HashTable是采用了向量加雙向連結清單的實作方式，向量在arBuckets變量儲存，向量包含多個bucket的指針，每個指針指向由多個bucket組成的雙向連結清單，新元素的加入使用前插法，即新元素總是在bucket的第一個位置。由上面可以看到，PHP的哈希表實作相當複雜。這是它使用超靈活的數組類型要付出的代價。

一個PHP中的HashTable的示例圖如下所示：

(圖檔源自網絡，侵權即删)

zend_hash_init zend_hash_add_or_update zend_hash_find zend_hash_del_key_or_index

函數執行步驟

設定哈希表大小 設定結構體其他成員變量的初始值 (包括釋放記憶體用的析構函數pDescructor)

詳細代碼注解點選：zend_hash_init源碼

注： 1、pHashFunction在此處并沒有用到，php的哈希函數使用的是内部的zend_inline_hash_func 2、zend_hash_init執行之後并沒有真正地為arBuckets配置設定記憶體和計算出nTableMask的大小，真正配置設定記憶體和計算nTableMask是在插入元素時進行CHECK_INIT檢查初始化時進行。

檢查鍵的長度 檢查初始化 計算哈希值和下标 周遊哈希值所在的bucket，如果找到相同的key且值需要更新，則更新資料，否則繼續指向bucket的下一個元素，直到指向bucket的最後一個位置 為新加入的元素配置設定bucket，設定新的bucket的屬性值，然後添加到哈希表中 如果哈希表空間滿了，則重新調整哈希表的大小

CONNECT_TO_BUCKET_DLLIST是将新元素添加到具有相同hash值的bucket連結清單。

CONNECT_TO_GLOBAL_DLLIST是将新元素添加到HashTable的雙向連結清單。

詳細代碼和注解請點選：zend_hash_add_or_update代碼注解。

周遊哈希值所在的bucket，如果找到key所在的bucket，則傳回值，否則，指向下一個bucket，直到指向bucket連結清單中的最後一個位置

詳細代碼和注解請點選：zend_hash_find代碼注解。

計算key的哈希值和下标 周遊哈希值所在的bucket，如果找到key所在的bucket，則進行第三步，否則，指向下一個bucket，直到指向bucket連結清單中的最後一個位置 如果要删除的是第一個元素，直接将arBucket[nIndex]指向第二個元素；其餘的操作是将目前指針的last的next執行目前的next 調整相關指針 釋放資料記憶體和bucket結構體記憶體

詳細代碼和注解請點選：zend_hash_del_key_or_index代碼注解。

PHP的哈希表的優點：PHP的HashTable為數組的操作提供了很大的友善，無論是數組的建立和新增元素或删除元素等操作，哈希表都提供了很好的性能，但其不足在資料量大的時候比較明顯，從時間複雜度和空間複雜度看看其不足。

不足如下：

儲存資料的結構體zval需要單獨配置設定記憶體，需要管理這個額外的記憶體，每個zval占用了16bytes的記憶體； 在新增bucket時，bucket也是額外配置設定，也需要16bytes的記憶體； 為了能進行順序周遊，使用雙向連結清單連接配接整個HashTable，多出了很多的指針，每個指針也要16bytes的記憶體； 在周遊時，如果元素位于bucket連結清單的尾部，也需要周遊完整個bucket連結清單才能找到所要查找的值

PHP的HashTable的不足主要是其雙向連結清單多出的指針及zval和bucket需要額外配置設定記憶體，是以導緻占用了很多記憶體空間及查找時多出了不少時間的消耗。

上面提到的不足，在PHP7中都很好地解決了，PHP7對核心中的資料結構做了一個大改造，使得PHP的效率高了很多，是以，推薦PHP開發者都将開發和部署版本更新吧。看看下面這段PHP代碼：

上面這個demo是有多個hash沖突時和無沖突時的時間消耗比較。筆者在PHP5.4下運作這段代碼，結果如下

插入 65536 個惡意的元素需要 43.72204709053 秒 插入 65536 個普通元素需要 0.009843111038208 秒

而在PHP7上運作的結果：

插入 65536 個惡意的元素需要 4.4028408527374 秒

插入 65536 個普通元素需要 0.0018510818481445 秒

可見不論在有沖突和無沖突的數組操作，PHP7的性能都提升了不少，當然，有沖突的性能提升更為明顯。至于為什麼PHP7的性能提高了這麼多，值得繼續深究。

最後再安利一下，筆者github上有一個簡易版的HashTable的實作：HashTable實作

原創文章，文筆有限，才疏學淺，文中若有不正之處，萬望告知。

如果本文對你有幫助，請點下推薦吧，謝謝_

參考文章：

PHP數組的Hash沖突執行個體

Understanding PHP's internal array implementation (PHP's Source Code for PHP Developers - Part 4)

PHP's new hashtable implementation