上圖是PHP5 hashtable的實現 新的zval結構 ```c struct _zval_struct { zend_value value; union { struct { ZEND_ENDIAN_LOHI_4( zend_uchar type, zend_uchar type_flags, zend_uchar const_flags, zend_uchar reserved ) } v; uint32_t type_info; } u1; union { uint32_t var_flags; uint32_t next; /* hash collision chain */ uint32_t cache_slot; /* literal cache slot */ uint32_t lineno; /* line number (for ast nodes) */ } u2; }; ``` 按照posix標準，一般整形對應的*_t類型為： 1字節?? ? uint8_t 2字節?? ? uint16_t 4字節?? ? uint32_t 8字節?? ? uint64_t PHP7中的zval結構包括三個部分。第一個是value。zend_value是一個聯合體。保存任何類型的數據 第二部分是是四個字節的typeinfo.包含真正變量的類型。 第三部分是一個聯合體。也是4個字節。輔助字段。 新的zval的實現不再使用引用計算。避免了兩次計數/ 新版HashTable的實現 ```c # 老版本 typedef struct bucket { ulong h; /* Used for numeric indexing */ uint nKeyLength; void *pData; void *pDataPtr; struct bucket *pListNext; /* 指向哈希鏈表中下一個元素 */ struct bucket *pListLast; /* 指向哈希鏈表中的前一個元素 */ struct bucket *pNext; /* 相同哈希值的下一個元素（哈希沖突用） */ struct bucket *pLast; /* 相同哈希值的上一個元素（哈希沖突用） */ const char *arKey; } Bucket; # PHP7 typedef struct _Bucket { zval val; zend_ulong h; /* hash value (or numeric index) */ zend_string *key; /* string key or NULL for numerics */ } Bucket; ``` 新的**HashTable**中，hash鏈表的構建工作由?**HashTable->arHash**?來承擔，而解決hash沖突的鏈表則被放到了**_zval_struct**了 h 是hash的值。key 是字符串 val 是值。 比如arr["hello"] = "111"; hash(hello) = h hello =k 111 = val ```c typedef struct _HashTable { union { struct { ZEND_ENDIAN_LOHI_3( zend_uchar flags, zend_uchar nApplyCount, /* 循環遍歷保護 */ uint16_t reserve) } v; uint32_t flags; } u; uint32_t nTableSize; /* hash表的大小 */ uint32_t nTableMask; /* 掩碼,用于根據hash值計算存儲位置,永遠等于nTableSize-1 */ uint32_t nNumUsed; /* arData數組已經使用的數量 */ uint32_t nNumOfElements; /* hash表中元素個數 */ uint32_t nInternalPointer; /* 用于HashTable遍歷 */ zend_long nNextFreeElement; /* 下一個空閑可用位置的數字索引 */ Bucket *arData; /* 存放實際數據 */ uint32_t *arHash; /* Hash表 */ dtor_func_t pDestructor; /* 析構函數 */ } HashTable; ``` HashTable中另外一個非常重要的值`arData`，這個值指向存儲元素數組的第一個Bucket HashTable中有兩個非常相近的值:`nNumUsed`、`nNumOfElements`，`nNumOfElements`表示哈希表已有元素數，那這個值不跟`nNumUsed`一樣嗎？為什么要定義兩個呢？實際上它們有不同的含義，當將一個元素從哈希表刪除時并不會將對應的Bucket移除，而是將Bucket存儲的zval標示為`IS_UNDEF`，只有擴容時發現nNumOfElements與nNumUsed相差達到一定數量(這個數量是:`ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)`)時才會將已刪除的元素全部移除，重新構建哈希表。所以`nNumUsed`>=`nNumOfElements`。 arData數組保存了所有的buckets（也就是數組的元素），這個數組被分配的內存大小為2的冪次方，它被保存在nTableSize這個字段（最小值為8）。數組中實際保存的元素的個數被保存在nNumOfElements這個字段。注意這個數組直接包含Bucket結構。老的Hashtable的實現是使用一個指針數組來保存分開分配的buckets，這意味著需要更多的分配和釋放操作（alloc/frees），需要為冗余信息及額外的指針分配內存。 ### hashtable 查找 arHash這個數組，這個數組由unit32_t類型的值組成。arHash數組跟arData的大小一樣（都是nTableSize），并且都被分配了一段連續的內存區塊。 hash函數（DJBX33A用于字符串的鍵，DJBX33A是PHP用到的一種hash算法）返回的hash值一般是32位或者64位的整型數，這個數有點大，不能直接作為hash數組的索引。首先通過求余操作將這個數調整到hashtable的大小的范圍之內。 求余是通過計算hash & (ht->nTableSize - 1) 參考資料 - [http://gywbd.github.io/posts/2014/12/php7-new-hashtable-implementation.html](http://gywbd.github.io/posts/2014/12/php7-new-hashtable-implementation.html) - [https://blog.csdn.net/pangudashu/article/details/53419992](https://blog.csdn.net/pangudashu/article/details/53419992) - [https://blog.csdn.net/heiyeshuwu/article/details/44259865](https://blog.csdn.net/heiyeshuwu/article/details/44259865)