上一節已經介紹了哈希表的基本原理并實現了一個基本的哈希表，而在實際項目中，對哈希表的需求遠不止那么簡單。對性能，靈活性都有不同的要求。下面我們看看PHP中的哈希表是怎么實現的。 ### PHP的哈希實現 PHP內核中的哈希表是十分重要的數據結構，PHP的大部分的語言特性都是基于哈希表實現的，例如：變量的作用域、函數表、類的屬性、方法等，Zend引擎內部的很多數據都是保存在哈希表中的。 #### 數據結構及說明 上一節提到PHP中的哈希表是使用拉鏈法來解決沖突的，具體點講就是使用鏈表來存儲哈希到同一個槽位的數據，Zend為了保存數據之間的關系使用了雙向列表來鏈接元素。 哈希表結構[]() PHP中的哈希表實現在Zend/zend_hash.c中，還是按照上一小節的方式，先看看PHP實現中的數據結構，PHP使用如下兩個數據結構來實現哈希表，HashTable結構體用于保存整個哈希表需要的基本信息，而Bucket結構體用于保存具體的數據內容，如下： typedef struct _hashtable { uint nTableSize; // hash Bucket的大小，最小為8，以2x增長。 uint nTableMask; // nTableSize-1 ， 索引取值的優化 uint nNumOfElements; // hash Bucket中當前存在的元素個數，count()函數會直接返回此值 ulong nNextFreeElement; // 下一個數字索引的位置 Bucket *pInternalPointer; // 當前遍歷的指針（foreach比for快的原因之一） Bucket *pListHead; // 存儲數組頭元素指針 Bucket *pListTail; // 存儲數組尾元素指針 Bucket **arBuckets; // 存儲hash數組 dtor_func_t pDestructor; // 在刪除元素時執行的回調函數，用于資源的釋放 zend_bool persistent; //指出了Bucket內存分配的方式。如果persisient為TRUE，則使用操作系統本身的內存分配函數為Bucket分配內存，否則使用PHP的內存分配函數。 unsigned char nApplyCount; // 標記當前hash Bucket被遞歸訪問的次數（防止多次遞歸） zend_bool bApplyProtection;// 標記當前hash桶允許不允許多次訪問，不允許時，最多只能遞歸3次 #if ZEND_DEBUG int inconsistent; #endif } HashTable; nTableSize字段用于標示哈希表的容量，哈希表的初始容量最小為8。首先看看哈希表的初始化函數: ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { uint i = 3; //... if (nSize >= 0x80000000) { /* prevent overflow */ ht->nTableSize = 0x80000000; } else { while ((1U << i) < nSize) { i++; } ht->nTableSize = 1 << i; } // ... ht->nTableMask = ht->nTableSize - 1; ? /* Uses ecalloc() so that Bucket* == NULL */ if (persistent) { tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *)); if (!tmp) { return FAILURE; } ht->arBuckets = tmp; } else { tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *)); if (tmp) { ht->arBuckets = tmp; } } ? return SUCCESS; } 例如如果設置初始大小為10，則上面的算法將會將大小調整為16。也就是始終將大小調整為接近初始大小的2的整數次方。 為什么會做這樣的調整呢？我們先看看HashTable將哈希值映射到槽位的方法，上一小節我們使用了取模的方式來將哈希值映射到槽位，例如大小為8的哈希表，哈希值為100， 則映射的槽位索引為: 100 % 8 = 4，由于索引通常從0開始，所以槽位的索引值為3，在PHP中使用如下的方式計算索引： h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; 從上面的_zend_hash_init()函數中可知，ht->nTableMask的大小為ht->nTableSize -1。這里使用&操作而不是使用取模，這是因為是相對來說取模操作的消耗和按位與的操作大很多。 > mask的作用就是將哈希值映射到槽位所能存儲的索引范圍內。 例如：某個key的索引值是21， 哈希表的大小為8，則mask為7，則求與時的二進制表示為： 10101 & 111 = 101 也就是十進制的5。 因為2的整數次方-1的二進制比較特殊：后面N位的值都是1，這樣比較容易能將值進行映射， 如果是普通數字進行了二進制與之后會影響哈希值的結果。那么哈希函數計算的值的平均分布就可能出現影響。 設置好哈希表大小之后就需要為哈希表申請存儲數據的空間了，如上面初始化的代碼，根據是否需要持久保存而調用了不同的內存申請方法。如前面PHP生命周期里介紹的,是否需要持久保存體現在：持久內容能在多個請求之間訪問，而非持久存儲是會在請求結束時釋放占用的空間。具體內容將在內存管理章節中進行介紹。 HashTable中的nNumOfElements字段很好理解，每插入一個元素或者unset刪掉元素時會更新這個字段。這樣在進行count()函數統計數組元素個數時就能快速的返回。 nNextFreeElement字段非常有用。先看一段PHP代碼： <?php $a = [array](http://www.php.net/array)(10 => 'Hello'); $a[] = 'TIPI'; [var_dump](http://www.php.net/var_dump)($a); ? // ouput [array](http://www.php.net/array)(2) { [10]=> string(5) "Hello" [11]=> string(5) "TIPI" } PHP中可以不指定索引值向數組中添加元素，這時將默認使用數字作為索引，和[C語言中的枚舉](http://en.wikipedia.org/wiki/Enumerated_type)類似，而這個元素的索引到底是多少就由nNextFreeElement字段決定了。如果數組中存在了數字key，則會默認使用最新使用的key + 1，例如上例中已經存在了10作為key的元素，這樣新插入的默認索引就為11了。 數據容器：槽位[]() 下面看看保存哈希表數據的槽位數據結構體： typedef struct bucket { ulong h; // 對char *key進行hash后的值，或者是用戶指定的數字索引值 uint nKeyLength; // hash關鍵字的長度，如果數組索引為數字，此值為0 void *pData; // 指向value，一般是用戶數據的副本，如果是指針數據，則指向pDataPtr void *pDataPtr; //如果是指針數據，此值會指向真正的value，同時上面pData會指向此值 struct bucket *pListNext; // 整個hash表的下一元素 struct bucket *pListLast; // 整個哈希表該元素的上一個元素 struct bucket *pNext; // 存放在同一個hash Bucket內的下一個元素 struct bucket *pLast; // 同一個哈希bucket的上一個元素 // 保存當前值所對于的key字符串，這個字段只能定義在最后，實現變長結構體 char arKey[1]; } Bucket; 如上面各字段的注釋。h字段保存哈希表key哈希后的值。這里保存的哈希值而不是在哈希表中的索引值，這是因為索引值和哈希表的容量有直接關系，如果哈希表擴容了，那么這些索引還得重新進行哈希在進行索引映射，這也是一種優化手段。在PHP中可以使用字符串或者數字作為數組的索引。數字索引直接就可以作為哈希表的索引，數字也無需進行哈希處理。h字段后面的nKeyLength字段是作為key長度的標示，如果索引是數字的話，則nKeyLength為0。在PHP數組中如果索引字符串可以被轉換成數字也會被轉換成數字索引。**所以在PHP中例如'10'，'11'這類的字符索引和數字索引10， 11沒有區別。** 上面結構體的最后一個字段用來保存key的字符串，而這個字段卻申明為只有一個字符的數組，其實這里是一種長見的[變長結構體](http://stackoverflow.com/a/4690976/319672)，主要的目的是增加靈活性。以下為哈希表插入新元素時申請空間的代碼 p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent); if (!p) { return FAILURE; } memcpy(p->arKey, arKey, nKeyLength); 如代碼，申請的空間大小加上了字符串key的長度，然后把key拷貝到新申請的空間里。在后面比如需要進行hash查找的時候就需要對比key這樣就可以通過對比p->arKey和查找的key是否一樣來進行數據的查找。申請空間的大小-1是因為結構體內本身的那個字節還是可以使用的。 > 在PHP5.4中將這個字段定義成const char* arKey類型了。  Zend引擎哈希表結構和關系 上圖來源于[網絡](http://gsm56.com/?p=124)。 - Bucket結構體維護了兩個雙向鏈表，pNext和pLast指針分別指向本槽位所在的鏈表的關系。 - 而pListNext和pListLast指針指向的則是整個哈希表所有的數據之間的鏈接關系。HashTable結構體中的pListHead和pListTail則維護整個哈希表的頭元素指針和最后一個元素的指針。 > PHP中數組的操作函數非常多，例如：array_shift()和array_pop()函數，分別從數組的頭部和尾部彈出元素。 哈希表中保存了頭部和尾部指針，這樣在執行這些操作時就能在常數時間內找到目標。 PHP中還有一些使用的相對不那么多的數組操作函數：next()，prev()等的循環中， 哈希表的另外一個指針就能發揮作用了：pInternalPointer，這個用于保存當前哈希表內部的指針。 這在循環時就非常有用。 如圖中左下角的假設，假設依次插入了Bucket1，Bucket2，Bucket3三個元素： 1. 插入Bucket1時，哈希表為空，經過哈希后定位到索引為1的槽位。此時的1槽位只有一個元素Bucket1。其中Bucket1的pData或者pDataPtr指向的是Bucket1所存儲的數據。此時由于沒有鏈接關系。pNext，pLast，pListNext，pListLast指針均為空。同時在HashTable結構體中也保存了整個哈希表的第一個元素指針，和最后一個元素指針，此時HashTable的pListHead和pListTail指針均指向Bucket1。 1. 插入Bucket2時，由于Bucket2的key和Bucket1的key出現沖突，此時將Bucket2放在雙鏈表的前面。由于Bucket2后插入并置于鏈表的前端，此時Bucket2.pNext指向Bucket1，由于Bucket2后插入。Bucket1.pListNext指向Bucket2，這時Bucket2就是哈希表的最后一個元素，這是HashTable.pListTail指向Bucket2。 1. 插入Bucket3，該key沒有哈希到槽位1，這時Bucket2.pListNext指向Bucket3，因為Bucket3后插入。同時HashTable.pListTail改為指向Bucket3。 簡單來說就是哈希表的Bucket結構維護了哈希表中插入元素的先后順序，哈希表結構維護了整個哈希表的頭和尾。在操作哈希表的過程中始終保持預算之間的關系。 #### 哈希表的操作接口 和上一節類似，將簡單介紹PHP哈希表的操作接口實現。提供了如下幾類操作接口： - 初始化操作，例如zend_hash_init()函數，用于初始化哈希表接口，分配空間等。 - 查找，插入，刪除和更新操作接口，這是比較常規的操作。 - 迭代和循環，這類的接口用于循環對哈希表進行操作。 - 復制，排序，倒置和銷毀等操作。 本小節選取其中的插入操作進行介紹。在PHP中不管是對數組的添加操作（zend_hash_add），還是對數組的更新操作（zend_hash_update），其最終都是調用_zend_hash_add_or_update函數完成，這在面向對象編程中相當于兩個公有方法和一個公共的私有方法的結構，以實現一定程度上的代碼復用。 ? ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC) { //...省略變量初始化和nKeyLength <=0 的異常處理 ? h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; ? p = ht->arBuckets[nIndex]; while (p != NULL) { if ((p->h == h) && (p->nKeyLength == nKeyLength)) { if (!memcmp(p->arKey, arKey, nKeyLength)) { // 更新操作 if (flag & HASH_ADD) { return FAILURE; } HANDLE_BLOCK_INTERRUPTIONS(); ? //..省略debug輸出 if (ht->pDestructor) { ht->pDestructor(p->pData); } UPDATE_DATA(ht, p, pData, nDataSize); if (pDest) { *pDest = p->pData; } HANDLE_UNBLOCK_INTERRUPTIONS(); return SUCCESS; } } p = p->pNext; } ? p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent); if (!p) { return FAILURE; } memcpy(p->arKey, arKey, nKeyLength); p->nKeyLength = nKeyLength; INIT_DATA(ht, p, pData, nDataSize); p->h = h; CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); //Bucket雙向鏈表操作 if (pDest) { *pDest = p->pData; } ? HANDLE_BLOCK_INTERRUPTIONS(); CONNECT_TO_GLOBAL_DLLIST(p, ht); // 將新的Bucket元素添加到數組的鏈接表的最后面 ht->arBuckets[nIndex] = p; HANDLE_UNBLOCK_INTERRUPTIONS(); ? ht->nNumOfElements++; ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* 如果此時數組的容量滿了，則對其進行擴容。*/ return SUCCESS; } 整個寫入或更新的操作流程如下： 1. 生成hash值，通過與nTableMask執行與操作，獲取在arBuckets數組中的Bucket。 1. 如果Bucket中已經存在元素，則遍歷整個Bucket，查找是否存在相同的key值元素，如果有并且是update調用，則執行update數據操作。 1. 創建新的Bucket元素，初始化數據，并將新元素添加到當前hash值對應的Bucket鏈表的最前面（CONNECT_TO_BUCKET_DLLIST）。 1. 將新的Bucket元素添加到數組的鏈接表的最后面（CONNECT_TO_GLOBAL_DLLIST）。 1. 將元素個數加1，如果此時數組的容量滿了，則對其進行擴容。這里的判斷是依據nNumOfElements和nTableSize的大小。如果nNumOfElements > nTableSize則會調用zend_hash_do_resize以2X的方式擴容（nTableSize << 1）。 ### 哈希表的性能 ### 其他語言中的HashTable實現 #### Ruby使用的st庫，Ruby中的兩種hash實現 ### 參考資料 [http://nikic.github.com/2012/03/28/Understanding-PHPs-internal-array-implementation.html](http://nikic.github.com/2012/03/28/Understanding-PHPs-internal-array-implementation.html)