目錄
- ⒈ 數據結構
- ⒉ 添加/修改元素
- ⒊ 刪除元素
- ⒋ 數組遍歷
- ⒌ hash 碰撞
- ⒍ 擴容
- ⒎ PHP 7 中的 packed hashtable
- 總結
從 PHP 5 到 PHP 7 ，PHP 通過對 hashtable 數據結構和實現方式的修改，使得數組在內存占用和性能上有了很大的提升。
⒈ 數據結構
// PHP 5 中 hashtable 的數據結構定義
typedef struct bucket {
ulong h; /*對于索引數組，存儲 key 的原始值；對于關聯數組，存儲 key 的 hash 之后的值*/
uint nKeyLength; /*關聯數組時存儲 key 的長度，索引數組此值為 0*/
void *pData; /*指向數組 value 的地址*/
void *pDataPtr; /*如果 value 為指針，則由 pDataPtr 記錄 vlaue，pData 則指向 pDataPtr*/
// PHP 5 中數組元素的順序是固定的，無論什么時候遍歷，數組元素總是與插入時的順序一致
// PHP 5 中使用雙向鏈表來保證數組元素的順序，pListNext 和 pListLast 分別按照
// 元素插入順序記錄當前 bucket 的下一個和上一個 bucket
struct bucket *pListNext;
struct bucket *pListLast;
// PHP 5 使用拉鏈法解決 hash 碰撞，pNext 和 pLast 分別存儲當前 bucket
// 在沖突的雙向鏈表中的下一個和上一個相鄰的 bucket
struct bucket *pNext;
struct bucket *pLast;
const char *arKey; /*關聯數組是存儲 key 的原始值*/
} Bucket;
typedef struct _hashtable {
uint nTableSize; /*當前 ht 所分配的 bucket 的總數，2^n*/
uint nTableMask; /*nTableSize - 1，用于計算索引*/
uint nNumOfElements; /*實際存儲的元素的數量*/
ulong nNextFreeElement; /*下一個可以被使用的整數 key*/
Bucket *pInternalPointer; /*數組遍歷時，記錄當前 bucket 的地址*/
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets; /*記錄 bucket 的 C 語言數組*/
dtor_func_t pDestructor; /*刪除數組元素時內部調用的函數*/
zend_bool persistent; /*標識 ht 是否永久有效*/
unsigned char nApplyCount; /*ht 允許的最大遞歸深度*/
zend_bool bApplyProtection; /*是否啟用遞歸保護*/
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
// PHP 7 中 hashtable 的數據結構
// PHP 7 中個子版本以及階段版本中對 hashtable 的數據結構的定義會有微小的差別，這里使用的是 PHP 7.4.0 中的定義
struct _zend_string {
zend_refcounted_h gc;
zend_ulong h; /*字符串 key 的 hash 值*/
size_t len; /*字符串 key 的長度*/
char val[1]; /*存儲字符串的值，利用了 struct hack*/
};
typedef struct _Bucket {
zval val; /*內嵌 zval 結構，存儲數組的 value 值*/
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
typedef struct _zend_array HashTable;
struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar _unused,
zend_uchar nIteratorsCount,
zend_uchar _unused2)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; /*作用與 PHP 5 中 hashtable 中 nTableMask 作用相同，但實現邏輯稍有變化*/
Bucket *arData; /*存儲 bucket 相關的信息*/
uint32_t nNumUsed; /*ht 中已經使用的 bucket 的數量，在 nNumOfElements 的基礎上加上刪除的 key*/
uint32_t nNumOfElements;
uint32_t nTableSize;
uint32_t nInternalPointer;
zend_long nNextFreeElement;
dtor_func_t pDestructor;
};
不考慮其他開銷，單從 Bucket 所占用的空間來看：在 PHP 5 中，考慮到內存對齊，一個 Bucket 占用的空間為 72 字節；在 PHP 7 中，一個 zend_value 占 8 字節，一個 zval 占 16 字節，一個 Bucket 占 32 字節。相比之下，PHP 7 中 Bucket 的內存空間消耗比 PHP 5 低了一半以上。
具體 PHP 5 數組的內存消耗情況，之前的文章已有講解，這里不再贅述
現在來談談 Bucket 的存儲：在 PHP 5 中，arBucket 是一個 C 語言數組，長度為 nTableSize，存儲的是指向 Bucket 的指針，發生 hash 碰撞的 Bucket 以雙向鏈表的方式連接。
在 PHP 7 中，Bucket 按照數組元素寫入的順序依次存儲，其索引值為 idx，該值存儲在 *arData 左側的映射區域中。idx 在映射區域中的索引為 nIndex，nIndex 值為負數，由數組 key 的 hash 值與 nTableMask 進行或運算得到。
// nTableMask 為 -2 倍的 nTableSize 的無符號表示
#define HT_SIZE_TO_MASK(nTableSize) \
((uint32_t)(-((nTableSize) + (nTableSize))))
// 在通過 idx 查找 Bucket 時，data 默認為 Bucket 類型，加 idx 表示向右偏移 idx 個 Bucket 位置
# define HT_HASH_TO_BUCKET_EX(data, idx) \
((data) + (idx))
// 在通過 nIndex 查找 idx 時，
// (uint32_t*)(data) 首先將 data 轉換成了 uint32_t* 類型的數組
// 然后將 nIndex 轉換成有符號數（負數），然后以數組的方式查找 idx 的值
#define HT_HASH_EX(data, idx) \
((uint32_t*)(data))[(int32_t)(idx)]
nIndex = h | ht->nTableMask;
idx = HT_HASH_EX(arData, nIndex);
p = HT_HASH_TO_BUCKET_EX(arData, idx);
這里需要指出，nTableMask 之所以設置為 nTableSize 的兩倍，是這樣在計算 nIndex 時可以減小 hash 碰撞的概率。
⒉ 添加/修改元素
PHP 5
先來談談 PHP 5 中數組元素的添加和修改，由于 PHP 5 中數組元素的插入順序以及 hash 碰撞都是通過雙向鏈表的方式來維護，所以雖然實現起來有些復雜，但理解起來相對容易一些。
// hash 碰撞雙向鏈表的維護
#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
(element)->pNext = (list_head); \
(element)->pLast = NULL; \
if ((element)->pNext) { \
(element)->pNext->pLast = (element); \
}
#define CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, last, next)\
(element)->pListLast = (last); \
(element)->pListNext = (next); \
if ((last) != NULL) { \
(last)->pListNext = (element); \
} else { \
(ht)->pListHead = (element); \
} \
if ((next) != NULL) { \
(next)->pListLast = (element); \
} else { \
(ht)->pListTail = (element); \
} \
// 數組元素插入順序雙向鏈表的維護
#define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, (ht)->pListTail, (Bucket *) NULL); \
if ((ht)->pInternalPointer == NULL) { \
(ht)->pInternalPointer = (element); \
}
// 數組元素的更新
#define UPDATE_DATA(ht, p, pData, nDataSize) \
if (nDataSize == sizeof(void*)) { \
// 值為指針類型的元素的更新 \
if ((p)->pData != (p)->pDataPtr) { \
pefree_rel((p)->pData, (ht)->persistent); \
} \
// pDataPtr 存儲元素值的地址，pData 存儲 pDataPtr 的地址 \
memcpy((p)->pDataPtr, pData, sizeof(void *)); \
(p)->pData = (p)->pDataPtr; \
} else { \
// 如果數組元素為值類型，則存入 pData，此時 pDataPtr 為 Null \
if ((p)->pData == (p)->pDataPtr) { \
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \
(p)->pDataPtr=NULL; \
} else { \
(p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \
/* (p)->pDataPtr is already NULL so no need to initialize it */ \
} \
memcpy((p)->pData, pData, nDataSize); \
}
// 數組元素的初始化
#define INIT_DATA(ht, p, _pData, nDataSize); \
if (nDataSize == sizeof(void*)) { \
// 指針類型元素的初始化 \
memcpy((p)->pDataPtr, (_pData), sizeof(void *)); \
(p)->pData = (p)->pDataPtr; \
} else { \
// 值類型元素的初始化 \
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
memcpy((p)->pData, (_pData), nDataSize); \
(p)->pDataPtr=NULL; \
}
// hashtable 初始化校驗，如果沒有初始化，則初始化 hashtable
#define CHECK_INIT(ht) do { \
if (UNEXPECTED((ht)->nTableMask == 0)) { \
(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent); \
(ht)->nTableMask = (ht)->nTableSize - 1; \
} \
} while (0)
// 數組元素的新增或更新（精簡掉了一些宏調用和代碼片段)
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)
{
ulong h;
uint nIndex;
Bucket *p;
CHECK_INIT(ht);
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if (p->arKey == arKey ||
((p->h == h) (p->nKeyLength == nKeyLength) !memcmp(p->arKey, arKey, nKeyLength))) {
// 數組元素更新邏輯
if (flag HASH_ADD) {
return FAILURE;
}
ZEND_ASSERT(p->pData != pData);
if (ht->pDestructor) {
ht->pDestructor(p->pData);
}
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
return SUCCESS;
}
p = p->pNext;
}
// 數組元素新增邏輯
if (IS_INTERNED(arKey)) {
p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
p->arKey = arKey;
} else {
p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
p->arKey = (const char*)(p + 1);
memcpy((char*)p->arKey, arKey, nKeyLength);
}
p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
// hash 碰撞鏈表維護
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
if (pDest) {
*pDest = p->pData;
}
// 數組元素寫入順序維護
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht->arBuckets[nIndex] = p;
ht->nNumOfElements++;
ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
return SUCCESS;
}
PHP 5 中的數組在新增或修改元素時，首先會根據給定的 key 計算得到相應的 hash 值，然后據此得到 arBuckets 的索引 nIndex，最終得到鏈表中第一個 Bucket（ hash 碰撞鏈表的表頭），即p。
如果是更新數組中已有的項，那么會從 p 開始遍歷 hash 碰撞鏈表，直到找到 arkey 與給定的 key 相同的 Bucket，然后更新 pData。
如果是向數組中新增項，首先會判斷給定的 key 是否為 interned string 類型，如果是，那么只需要為 Bucket 申請內存，然后將 p->arKey 指向給定的 key 的地址即可，否則在為新的 Bucket 申請內存的同時還需要為給定的 key 申請內存，然后將 p->arKey 指向為 key 申請的內存的地址。之后會對新申請的 Bucket 進行初始化，最后要做的兩件事：維護 hash 碰撞鏈表和數組元素寫入順序鏈表。在維護 hash 碰撞的鏈表時，新增的 Bucket 是放在鏈表頭的位置；維護數組元素寫入順序的鏈表時，新增的 Bucket 是放在鏈表的末尾，同時將 hashtable 的 pListTail 指向新增的 Bucket。
關于 PHP 中的 interned string，之前在講解 PHP 7 對字符串處理邏輯優化的時候已經說明，這里不再贅述
PHP 7
PHP 7 在 hashtable 的數據結構上做了比較大的改動，同時放棄了使用雙向鏈表的方式來維護 hash 碰撞和數組元素的寫入順序，在內存管理以及性能上得到了提升，但理解起來卻不如 PHP 5 中的實現方式直觀。
#define Z_NEXT(zval) (zval).u2.next
#define HT_HASH_EX(data, idx) \
((uint32_t*)(data))[(int32_t)(idx)]
# define HT_IDX_TO_HASH(idx) \
((idx) * sizeof(Bucket))
// PHP 7 中數組添加/修改元素（精簡了部分代碼）
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag)
{
zend_ulong h;
uint32_t nIndex;
uint32_t idx;
Bucket *p, *arData;
/*... ...*/
ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
add_to_hash:
idx = ht->nNumUsed++;
ht->nNumOfElements++;
arData = ht->arData;
p = arData + idx;
p->key = key;
p->h = h = ZSTR_H(key);
nIndex = h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
ZVAL_COPY_VALUE(p->val, pData);
return p->val;
}
這里需要先說明一下 nNumUsed 和 nNumOfElements 的區別：
按圖中示例，此時 nNumUsed 的值應該為 5，但 nNumOfElements 的值則應該為 3。在 PHP 7 中，數組元素按照寫入順序依次存儲，而 nNumUsed 正好可以用來充當數組元素存儲位置索引的功能。
另外就是 p = arData + idx ，前面已經講過 arData 為 Bucket 類型，這里 +idx 意為指針從 arData 的位置開始向右偏移 idx 個 Bucket 的位置。宏調用 HT_HASH_EX 也是同樣的道理。
最后就是 Z_NEXT(p->val)，PHP 7 中的 Bucket 結構都內嵌了一個 zval，zval 中的聯合體 u2 中有一項 next 用來記錄hash 碰撞的信息。nIndex 用來標識 idx 在映射表中的位置，在往 hashtable 中新增元素時，如果根據給定的 key 計算得到的 nIndex 的位置已經有值（即發生了 hash 碰撞），那么此時需要將 nIndex 所指向的位置的原值記錄到新增的元素所對應的 Bucket 下的 val.u2.next 中。宏調用 HT_IDX_TO_HASH 的作用是根據 idx 計算得到 Bucket 的以字節為單位的偏移量。
⒊ 刪除元素
PHP 5
在 PHP 5 中，數組元素的刪除過程中的主要工作是維護 hash 碰撞鏈表和數組元素寫入順序的鏈表。
// 刪除 Bucket 的代碼（精簡了部分代碼片段）
static zend_always_inline void i_zend_hash_bucket_delete(HashTable *ht, Bucket *p)
{
if (p->pLast) {
p->pLast->pNext = p->pNext;
} else {
ht->arBuckets[p->h ht->nTableMask] = p->pNext;
}
if (p->pNext) {
p->pNext->pLast = p->pLast;
}
if (p->pListLast != NULL) {
p->pListLast->pListNext = p->pListNext;
} else {
/* Deleting the head of the list */
ht->pListHead = p->pListNext;
}
if (p->pListNext != NULL) {
p->pListNext->pListLast = p->pListLast;
} else {
/* Deleting the tail of the list */
ht->pListTail = p->pListLast;
}
if (ht->pInternalPointer == p) {
ht->pInternalPointer = p->pListNext;
}
ht->nNumOfElements--;
if (ht->pDestructor) {
ht->pDestructor(p->pData);
}
if (p->pData != p->pDataPtr) {
pefree(p->pData, ht->persistent);
}
pefree(p, ht->persistent);
}
// 元素刪除
ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
{
uint nIndex;
Bucket *p;
if (flag == HASH_DEL_KEY) {
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)
((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
|| !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
i_zend_hash_bucket_delete(ht, p);
return SUCCESS;
}
p = p->pNext;
}
return FAILURE;
}
PHP 5 中數組在刪除元素時，仍然是先根據給定的 key 計算 hash，然后找到 arBucket 的 nIndex，最終找到需要刪除的 Bucket 所在的 hash 碰撞的鏈表，通過遍歷鏈表，找到最終需要刪除的 Bucket。
在實際刪除 Bucket 的過程中，主要做的就是維護兩個鏈表：hash 碰撞鏈表和數組元素寫入順序鏈表。再就是釋放內存。
PHP 7
由于 PHP 7 記錄 hash 碰撞信息的方式發生了變化，所以在刪除元素時處理 hash 碰撞鏈表的邏輯也會有所不同。另外，在刪除元素時，還有可能會遇到空間回收的情況。
#define IS_UNDEF 0
#define Z_TYPE_INFO(zval) (zval).u1.type_info
#define Z_TYPE_INFO_P(zval_p) Z_TYPE_INFO(*(zval_p))
#define ZVAL_UNDEF(z) do { \
Z_TYPE_INFO_P(z) = IS_UNDEF; \
} while (0)
static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
{
// 從 hash 碰撞鏈表中刪除指定的 Bucket
if (!(HT_FLAGS(ht) HASH_FLAG_PACKED)) {
if (prev) {
Z_NEXT(prev->val) = Z_NEXT(p->val);
} else {
HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);
}
}
idx = HT_HASH_TO_IDX(idx);
ht->nNumOfElements--;
if (ht->nInternalPointer == idx || UNEXPECTED(HT_HAS_ITERATORS(ht))) {
// 如果當前 hashtable 的內部指針指向了要刪除的 Bucket 或當前 hashtable 有遍歷
// 操作，那么需要避開當前正在被刪除的 Bucket
uint32_t new_idx;
new_idx = idx;
while (1) {
new_idx++;
if (new_idx >= ht->nNumUsed) {
break;
} else if (Z_TYPE(ht->arData[new_idx].val) != IS_UNDEF) {
break;
}
}
if (ht->nInternalPointer == idx) {
ht->nInternalPointer = new_idx;
}
zend_hash_iterators_update(ht, idx, new_idx);
}
if (ht->nNumUsed - 1 == idx) {
//如果被刪除的 Bucket 在數組的末尾，則同時回收與 Bucket 相鄰的已經被刪除的 Bucket 的空間
do {
ht->nNumUsed--;
} while (ht->nNumUsed > 0 (UNEXPECTED(Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)));
ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed);
}
if (p->key) {
// 刪除 string 類型的索引
zend_string_release(p->key);
}
// 刪除 Bucket
if (ht->pDestructor) {
zval tmp;
ZVAL_COPY_VALUE(tmp, p->val);
ZVAL_UNDEF(p->val);
ht->pDestructor(tmp);
} else {
ZVAL_UNDEF(p->val);
}
}
static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint32_t idx, Bucket *p)
{
Bucket *prev = NULL;
if (!(HT_FLAGS(ht) HASH_FLAG_PACKED)) {
// 如果被刪除的 Bucket 存在 hash 碰撞的情況，那么需要找出其在 hash 碰撞鏈表中的位置
uint32_t nIndex = p->h | ht->nTableMask;
uint32_t i = HT_HASH(ht, nIndex);
if (i != idx) {
prev = HT_HASH_TO_BUCKET(ht, i);
while (Z_NEXT(prev->val) != idx) {
i = Z_NEXT(prev->val);
prev = HT_HASH_TO_BUCKET(ht, i);
}
}
}
_zend_hash_del_el_ex(ht, idx, p, prev);
}
ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p)
{
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
_zend_hash_del_el(ht, HT_IDX_TO_HASH(p - ht->arData), p);
}
PHP 7 中數組元素的刪除，其最終目的是刪除指定的 Bucket。在刪除 Bucket 時還需要處理好 hash 碰撞鏈表維護的問題。由于 PHP 7 中 hash 碰撞只維護了一個單向鏈表（通過 Bucket.val.u2.next 來維護），所以在刪除 Bucket 時還需要找出 hash 碰撞鏈表中的前一項 prev。最后，在刪除 Bucket 時如果當前的 hashtable 的內部指針（nInternalPointer）正好指向了要刪除的 Bucket 或存在遍歷操作，那么需要改變內部指針的指向，同時在遍歷時跳過要刪除的 Bucket。另外需要指出的是，并不是每一次刪除 Bucket 的操作都會回收相應的內存空間，通常刪除 Bucket 只是將其中 val 的類型標記為 IS_UNDEF，只有在擴容或要刪除的 Bucket 為最后一項并且相鄰的 Bucket 為 IS_UNDEF 時才會回收其內存空間。
⒋ 數組遍歷
PHP 5
由于 PHP 5 中有專門用來記錄數組元素寫入順序的雙向鏈表，所以數組的遍歷邏輯相對比較簡單。
// 數組的正向遍歷
ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
{
HashPosition *current = pos ? pos : ht->pInternalPointer;
IS_CONSISTENT(ht);
if (*current) {
*current = (*current)->pListNext;
return SUCCESS;
} else
return FAILURE;
}
// 數組的反向遍歷
ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
{
HashPosition *current = pos ? pos : ht->pInternalPointer;
IS_CONSISTENT(ht);
if (*current) {
*current = (*current)->pListLast;
return SUCCESS;
} else
return FAILURE;
}
emsp； PHP 5 中 hashtable 的數據結構中有三個字段：pInternalPointer 用來記錄數組遍歷過程中指針指向的當前 Bucket 的地址；pListHead 用來記錄保存數組元素寫入順序的雙向鏈表的表頭；pListTail 用來記錄保存數組元素寫入順序的雙向鏈表的表尾。數組的正向遍歷從 pListHead 的位置開始，通過不斷更新 pInternalPointer 來實現；反向遍歷從 pListTail 開始，通過不斷更新 pInternalPointer 來實現。
PHP 7
由于 PHP 7 中數組的元素是按照寫入的順序存儲，所以遍歷的邏輯相對簡單，只是在遍歷過程中需要跳過被標記為 IS_UNDEF 的項。
⒌ hash 碰撞
PHP 5
前面在談論數組元素添加/修改的時候已有提及，每次在數組新增元素時，都會檢查并處理 hash 碰撞，即 CONNECT_TO_BUCKET_DLLIST，代碼如下
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
(element)->pNext = (list_head); \
(element)->pLast = NULL; \
if ((element)->pNext) { \
(element)->pNext->pLast = (element); \
}
在新增元素時，如果當前 arBuckets 的位置沒有其他元素，那么只需要直接寫入新增的 Bucket 即可，否則新增的 Bucket 會被寫入 hash 碰撞雙向鏈表的表頭位置。
PHP 7
前面已經講過，PHP 7 中的 hashtable 是通過 Bucket 中的 val.u2.next 項來維護 hash 碰撞的單向鏈表的。所以，在往 hashtable 中添加新的元素時，最后需要先將 nIndex 位置的值寫入新增的 Bucket 的 val.u2.next 中。而在刪除 Bucket 時，需要同時找出要刪除的 Bucket 所在的 hash 碰撞鏈表中的前一項，以便后續的 hash 碰撞鏈表的維護。
⒍ 擴容
PHP 5
在數組元素新增/修改的 API 中的最后有一行代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht) 來判斷當前 hashtable 是否需要擴容，如果需要則對其進行擴容。
// 判斷當前 hashtable 是否需要擴容
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)->nNumOfElements > (ht)->nTableSize) { \
zend_hash_do_resize(ht); \
}
// hashtable 擴容（精簡部分代碼）
ZEND_API int zend_hash_do_resize(HashTable *ht)
{
Bucket **t;
if ((ht->nTableSize 1) > 0) { /* Let's double the table size */
t = (Bucket **) perealloc(ht->arBuckets, (ht->nTableSize 1) * sizeof(Bucket *), ht->persistent);
ht->arBuckets = t;
ht->nTableSize = (ht->nTableSize 1);
ht->nTableMask = ht->nTableSize - 1;
zend_hash_rehash(ht);
}
}
// 擴容后對 hashtable 中的元素進行 rehash（精簡部分代碼）
ZEND_API int zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint nIndex;
if (UNEXPECTED(ht->nNumOfElements == 0)) {
return SUCCESS;
}
memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
for (p = ht->pListHead; p != NULL; p = p->pListNext) {
nIndex = p->h ht->nTableMask;
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
ht->arBuckets[nIndex] = p;
}
return SUCCESS;
}
首先，PHP 5 hashtable 擴容的前提條件：數組中元素的數量超過 hashtable 的 nTableSize 的值。之后，hashtable 的 nTableSize 會翻倍，然后重新為 arBuckets 分配內存空間并且更新 nTableMask 的值。最后，由于 nTableMask 發生變化，需要根據數組元素的索引重新計算 nIndex，然后將之前的 Bucket 關聯到新分配的 arBuckets 中新的位置。
PHP 7
在 PHP 7 的新增/修改 hashtable 的 API 中也有判斷是否需要擴容的代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht)，當滿足條件時則會執行擴容操作。
#define HT_SIZE_TO_MASK(nTableSize) \
((uint32_t)(-((nTableSize) + (nTableSize))))
#define HT_HASH_SIZE(nTableMask) \
(((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_DATA_SIZE(nTableSize) \
((size_t)(nTableSize) * sizeof(Bucket))
#define HT_SIZE_EX(nTableSize, nTableMask) \
(HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask)))
#define HT_SET_DATA_ADDR(ht, ptr) do { \
(ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
} while (0)
#define HT_GET_DATA_ADDR(ht) \
((char*)((ht)->arData) - HT_HASH_SIZE((ht)->nTableMask))
// 當 hashtable 的 nNumUsed 大于或等于 nTableSize 時則執行擴容操作
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)->nNumUsed >= (ht)->nTableSize) { \
zend_hash_do_resize(ht); \
}
# define HT_HASH_RESET(ht) \
memset(HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))
#define HT_IS_WITHOUT_HOLES(ht) \
((ht)->nNumUsed == (ht)->nNumOfElements)
// 擴容（精簡部分代碼）
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
zend_hash_rehash(ht);
} else if (ht->nTableSize HT_MAX_SIZE) { /* Let's double the table size */
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
uint32_t nSize = ht->nTableSize + ht->nTableSize;
Bucket *old_buckets = ht->arData;
ht->nTableSize = nSize;
new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) IS_ARRAY_PERSISTENT);
ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize);
HT_SET_DATA_ADDR(ht, new_data);
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
pefree(old_data, GC_FLAGS(ht) IS_ARRAY_PERSISTENT);
zend_hash_rehash(ht);
} else {
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
}
}
// rehash（精簡部分代碼）
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint32_t nIndex, i;
if (UNEXPECTED(ht->nNumOfElements == 0)) {
if (!(HT_FLAGS(ht) HASH_FLAG_UNINITIALIZED)) {
ht->nNumUsed = 0;
HT_HASH_RESET(ht);
}
return SUCCESS;
}
HT_HASH_RESET(ht);
i = 0;
p = ht->arData;
if (HT_IS_WITHOUT_HOLES(ht)) {
// Bucket 中沒有被標記為 IS_UNDEF 的項
do {
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i ht->nNumUsed);
} else {
// Bucket 中有被標記為 IS_UNDEF 的項
uint32_t old_num_used = ht->nNumUsed;
do {
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
// Bucket 中第一項被標記為 IS_UNDEF
uint32_t j = i;
Bucket *q = p;
if (EXPECTED(!HT_HAS_ITERATORS(ht))) {
// hashtable 沒有遍歷操作
while (++i ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(q->val, p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
q++;
j++;
}
}
} else {
// hashtable 存在遍歷操作
uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0);
while (++i ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(q->val, p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
if (UNEXPECTED(i >= iter_pos)) {
do {
zend_hash_iterators_update(ht, iter_pos, j);
iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
} while (iter_pos i);
}
q++;
j++;
}
}
}
ht->nNumUsed = j;
break;
}
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i ht->nNumUsed);
/* Migrate pointer to one past the end of the array to the new one past the end, so that
* newly inserted elements are picked up correctly. */
if (UNEXPECTED(HT_HAS_ITERATORS(ht))) {
_zend_hash_iterators_update(ht, old_num_used, ht->nNumUsed);
}
}
return SUCCESS;
}
PHP 7 中 hashtable 在擴容時也是將 nTableSize 翻倍，然后進行 rehash。在進行 rehash 操作時，如果 Bucket 中沒有標記為刪除的項（IS_UNDEF），那么 rehash 操作之后 Bucket 的存儲順序不會發生任何變化，只是 idx 索引存儲的位置會因為 nTableMask 的變化而變化，最終導致 hash 碰撞鏈表的變化。如果 Bucket 中存在被標記為刪除的項，那么在 rehash 的過程中會跳過這些 Bucket 項，只保留那些沒有被刪除的項。同時，由于這樣會導致 Bucket 的索引相較于原來發生變化，所以在 rehash 的過程中需要同時更新 hashtable 內部指針的信息以及與遍歷操作相關的信息。
⒎ PHP 7 中的 packed hashtable
在 PHP 7 中，如果一個數組為索引數組，并且數組中的索引為升序排列，那么此時由于 hashtable 中 Bucket 按照寫入順序排列，而數組索引也是升序的，所以映射表已經沒有必要。PHP 7 針對這種特殊的情況對 hashtable 做了一些優化 packed hashtable。
#define HT_MIN_MASK ((uint32_t) -2)
#define HT_MIN_SIZE 8
#define HT_HASH_RESET_PACKED(ht) do { \
HT_HASH(ht, -2) = HT_INVALID_IDX; \
HT_HASH(ht, -1) = HT_INVALID_IDX; \
} while (0)
static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht)
{
void *data;
if (UNEXPECTED(GC_FLAGS(ht) IS_ARRAY_PERSISTENT)) {
data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), 1);
} else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) {
data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
} else {
data = emalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK));
}
HT_SET_DATA_ADDR(ht, data);
/* Don't overwrite iterator count. */
ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
HT_HASH_RESET_PACKED(ht);
}
packed hashtable 在初始化時，nTableMask 的值默認為 -2，同時在 hashtable 的 flags 中會進行相應的標記。如果此時 packed hashtable 中沒有任何元素，那么 nTableSize 會設為 0。
static void ZEND_FASTCALL zend_hash_packed_grow(HashTable *ht)
{
HT_ASSERT_RC1(ht);
if (ht->nTableSize >= HT_MAX_SIZE) {
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket), sizeof(Bucket));
}
ht->nTableSize += ht->nTableSize;
HT_SET_DATA_ADDR(ht, perealloc2(HT_GET_DATA_ADDR(ht), HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), HT_USED_SIZE(ht), GC_FLAGS(ht) IS_ARRAY_PERSISTENT));
}
另外，packed hashtable 在擴容時，只需要將 nTableSize 翻倍，同時由于索引是升序排列的，所以 Bucket 的順序不需要做任何調整，只需要重新分配內存空間即可。
需要強調的是，packed hashtable 只適用于索引為升序排列的索引數組（索引不一定要連續，中間可以有間隔）。如果索引數組的索引順序被破壞，或索引中加入了字符串索引，那么此時 packed hashtable 會被轉換為普通的 hashtable。
總結
到此這篇關于PHP5和PHP7中數組實現方式比較的文章就介紹到這了,更多相關PHP5和PHP7數組實現比較內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- PHP7.1方括號數組符號多值復制及指定鍵值賦值用法分析
- PHP7常量數組用法分析
- PHP7數組的底層實現示例
- php5.5新數組函數array_column使用
