PHP內核探索之PHP中的哈希表
在PHP內核中，其中一個很重要的數據結構就是HashTable。我們常用的數組，在內核中就是用HashTable來實現。那么，PHP的HashTable是怎么實現的呢？最近在看HashTable的數據結構，但是算法書籍里面沒有具體的實現算法，剛好最近也在閱讀PHP的源碼，于是參考PHP的HashTable的實現，自己實現了一個簡易版的HashTable，總結了一些心得，下面給大家分享一下。
筆者github上有一個簡易版的HashTable的實現：HashTable實現
另外，我在github有對PHP源碼更詳細的注解。感興趣的可以圍觀一下，給個star。PHP5.4源碼注解。可以通過commit記錄查看已添加的注解。
HashTable的介紹
哈希表是實現字典操作的一種有效數據結構。
定義
簡單地說，HashTable(哈希表)就是一種鍵值對的數據結構。支持插入，查找，刪除等操作。在一些合理的假設下，在哈希表中的所有操作的時間復雜度是O(1)(對相關證明感興趣的可以自行查閱)。
實現哈希表的關鍵
在哈希表中，不是使用關鍵字做下標，而是通過哈希函數計算出key的哈希值作為下標，然后查找/刪除時再計算出key的哈希值，從而快速定位元素保存的位置。
在一個哈希表中，不同的關鍵字可能會計算得到相同的哈希值，這叫做“哈希沖突”，就是處理兩個或多個鍵的哈希值相同的情況。解決哈希沖突的方法有很多，開放尋址法，拉鏈法等等。
因此，實現一個好的哈希表的關鍵就是一個好的哈希函數和處理哈希沖突的方法。
Hash函數
判斷一個哈希算法的好壞有以下四個定義： > * 一致性，等價的鍵必然產生相等的哈希值； > * 高效性，計算簡便； > * 均勻性，均勻地對所有的鍵進行哈希。
哈希函數建立了關鍵值與哈希值的對應關系，即：h = hash_func(key)。對應關系見下圖：
設計一個完美的哈希函數就交由專家去做吧，我們只管用已有的較成熟的哈希函數就好了。PHP內核使用的哈希函數是time33函數，又叫DJBX33A，其實現如下：
- 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;
- }
注：函數使用了一個8次循環+switch來實現，是對for循環的優化，減少循環的運行次數，然后在switch里面執行剩下的沒有遍歷到的元素。
拉鏈法
將所有具有相同哈希值的元素都保存在一條鏈表中的方法叫拉鏈法。查找的時候通過先計算key對應的哈希值，然后根據哈希值找到對應的鏈表，最后沿著鏈表順序查找相應的值。 具體保存后的結構圖如下：
PHP的HashTable結構
簡單地介紹了哈希表的數據結構之后，繼續看看PHP中是如何實現哈希表的。
- 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的倍數增長
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，然后只取哈希表的低位。
hash | 193491849 | 0b1011100010000111001110001001
& mask | & 63 | & 0b0000000000000000000000111111
----------------------------------------------------------------------
= index | = 9 | = 0b0000000000000000000000001001
因此，在哈希表中，foo是保存在arBuckets中下標為9的bucket向量中。
bucket結構體的定義
- 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，哈希值（或數字鍵值的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的示例圖如下所示：
HashTable相關API
zend_hash_init
zend_hash_add_or_update
zend_hash_find
zend_hash_del_key_or_index
zend_hash_init
函數執行步驟
設置哈希表大小
設置結構體其他成員變量的初始值 (包括釋放內存用的析構函數pDescructor)
詳細代碼注解點擊：zend_hash_init源碼
注：
1、pHashFunction在此處并沒有用到，php的哈希函數使用的是內部的zend_inline_hash_func
2、zend_hash_init執行之后并沒有真正地為arBuckets分配內存和計算出nTableMask的大小，真正分配內存和計算nTableMask是在插入元素時進行CHECK_INIT檢查初始化時進行。
zend_hash_add_or_update
函數執行步驟
檢查鍵的長度
檢查初始化
計算哈希值和下標
遍歷哈希值所在的bucket，如果找到相同的key且值需要更新，則更新數據，否則繼續指向bucket的下一個元素，直到指向bucket的最后一個位置
為新加入的元素分配bucket，設置新的bucket的屬性值，然后添加到哈希表中
如果哈希表空間滿了，則重新調整哈希表的大小
函數執行流程圖
CONNECT_TO_BUCKET_DLLIST是將新元素添加到具有相同hash值的bucket鏈表。
CONNECT_TO_GLOBAL_DLLIST是將新元素添加到HashTable的雙向鏈表。
詳細代碼和注解請點擊：zend_hash_add_or_update代碼注解。
zend_hash_find
函數執行步驟
計算哈希值和下標
遍歷哈希值所在的bucket，如果找到key所在的bucket，則返回值，否則，指向下一個bucket，直到指向bucket鏈表中的最后一個位置
詳細代碼和注解請點擊：zend_hash_find代碼注解。
zend_hash_del_key_or_index
函數執行步驟
計算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代碼：
- <?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下運行這段代碼，結果如下
插入 65536 個惡意的元素需要 43.72204709053 秒
插入 65536 個普通元素需要 0.009843111038208 秒
而在PHP7上運行的結果：
插入 65536 個惡意的元素需要 4.4028408527374 秒
插入 65536 個普通元素需要 0.0018510818481445 秒
可見不論在有沖突和無沖突的數組操作，PHP7的性能都提升了不少，當然，有沖突的性能提升更為明顯。至于為什么PHP7的性能提高了這么多，值得繼續深究。
參考文章：
Understanding PHP’s internal array implementation (PHP’s Source Code for PHP Developers – Part 4)
