您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)PHP5和PHP7中數(shù)組實現(xiàn)方式有什么不同的內(nèi)容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
// PHP 5 中 hashtable 的數(shù)據(jù)結(jié)構(gòu)定義 typedef struct bucket { ulong h; /*對于索引數(shù)組,存儲 key 的原始值;對于關(guān)聯(lián)數(shù)組,存儲 key 的 hash 之后的值*/ uint nKeyLength; /*關(guān)聯(lián)數(shù)組時存儲 key 的長度,索引數(shù)組此值為 0*/ void *pData; /*指向數(shù)組 value 的地址*/ void *pDataPtr; /*如果 value 為指針,則由 pDataPtr 記錄 vlaue,pData 則指向 pDataPtr*/ // PHP 5 中數(shù)組元素的順序是固定的,無論什么時候遍歷,數(shù)組元素總是與插入時的順序一致 // PHP 5 中使用雙向鏈表來保證數(shù)組元素的順序,pListNext 和 pListLast 分別按照 // 元素插入順序記錄當(dāng)前 bucket 的下一個和上一個 bucket struct bucket *pListNext; struct bucket *pListLast; // PHP 5 使用拉鏈法解決 hash 碰撞,pNext 和 pLast 分別存儲當(dāng)前 bucket // 在沖突的雙向鏈表中的下一個和上一個相鄰的 bucket struct bucket *pNext; struct bucket *pLast; const char *arKey; /*關(guān)聯(lián)數(shù)組是存儲 key 的原始值*/ } Bucket; typedef struct _hashtable { uint nTableSize; /*當(dāng)前 ht 所分配的 bucket 的總數(shù),2^n*/ uint nTableMask; /*nTableSize - 1,用于計算索引*/ uint nNumOfElements; /*實際存儲的元素的數(shù)量*/ ulong nNextFreeElement; /*下一個可以被使用的整數(shù) key*/ Bucket *pInternalPointer; /*數(shù)組遍歷時,記錄當(dāng)前 bucket 的地址*/ Bucket *pListHead; Bucket *pListTail; Bucket **arBuckets; /*記錄 bucket 的 C 語言數(shù)組*/ dtor_func_t pDestructor; /*刪除數(shù)組元素時內(nèi)部調(diào)用的函數(shù)*/ zend_bool persistent; /*標(biāo)識 ht 是否永久有效*/ unsigned char nApplyCount; /*ht 允許的最大遞歸深度*/ zend_bool bApplyProtection; /*是否啟用遞歸保護(hù)*/ #if ZEND_DEBUG int inconsistent; #endif } HashTable; // PHP 7 中 hashtable 的數(shù)據(jù)結(jié)構(gòu) // PHP 7 中個子版本以及階段版本中對 hashtable 的數(shù)據(jù)結(jié)構(gòu)的定義會有微小的差別,這里使用的是 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; /*內(nèi)嵌 zval 結(jié)構(gòu),存儲數(shù)組的 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 作用相同,但實現(xiàn)邏輯稍有變化*/ Bucket *arData; /*存儲 bucket 相關(guān)的信息*/ uint32_t nNumUsed; /*ht 中已經(jīng)使用的 bucket 的數(shù)量,在 nNumOfElements 的基礎(chǔ)上加上刪除的 key*/ uint32_t nNumOfElements; uint32_t nTableSize; uint32_t nInternalPointer; zend_long nNextFreeElement; dtor_func_t pDestructor; };
??不考慮其他開銷,單從 Bucket 所占用的空間來看:在 PHP 5 中,考慮到內(nèi)存對齊,一個 Bucket 占用的空間為 72 字節(jié);在 PHP 7 中,一個 zend_value 占 8 字節(jié),一個 zval 占 16 字節(jié),一個 Bucket 占 32 字節(jié)。相比之下,PHP 7 中 Bucket 的內(nèi)存空間消耗比 PHP 5 低了一半以上。
具體 PHP 5 數(shù)組的內(nèi)存消耗情況,之前的文章已有講解,這里不再贅述
??現(xiàn)在來談?wù)?Bucket 的存儲:在 PHP 5 中,arBucket 是一個 C 語言數(shù)組,長度為 nTableSize,存儲的是指向 Bucket 的指針,發(fā)生 hash 碰撞的 Bucket 以雙向鏈表的方式連接。
??在 PHP 7 中,Bucket 按照數(shù)組元素寫入的順序依次存儲,其索引值為 idx,該值存儲在 *arData 左側(cè)的映射區(qū)域中。idx 在映射區(qū)域中的索引為 nIndex,nIndex 值為負(fù)數(shù),由數(shù)組 key 的 hash 值與 nTableMask 進(jìn)行或運算得到。
// nTableMask 為 -2 倍的 nTableSize 的無符號表示 #define HT_SIZE_TO_MASK(nTableSize) \ ((uint32_t)(-((nTableSize) + (nTableSize)))) // 在通過 idx 查找 Bucket 時,data 默認(rèn)為 Bucket 類型,加 idx 表示向右偏移 idx 個 Bucket 位置 # define HT_HASH_TO_BUCKET_EX(data, idx) \ ((data) + (idx)) // 在通過 nIndex 查找 idx 時, // (uint32_t*)(data) 首先將 data 轉(zhuǎn)換成了 uint32_t* 類型的數(shù)組 // 然后將 nIndex 轉(zhuǎn)換成有符號數(shù)(負(fù)數(shù)),然后以數(shù)組的方式查找 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 之所以設(shè)置為 nTableSize 的兩倍,是這樣在計算 nIndex 時可以減小 hash 碰撞的概率。
PHP 5
??先來談?wù)?PHP 5 中數(shù)組元素的添加和修改,由于 PHP 5 中數(shù)組元素的插入順序以及 hash 碰撞都是通過雙向鏈表的方式來維護(hù),所以雖然實現(xiàn)起來有些復(fù)雜,但理解起來相對容易一些。
// hash 碰撞雙向鏈表的維護(hù) #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); \ } \ // 數(shù)組元素插入順序雙向鏈表的維護(hù) #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); \ } // 數(shù)組元素的更新 #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 { \ // 如果數(shù)組元素為值類型,則存入 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); \ } // 數(shù)組元素的初始化 #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) // 數(shù)組元素的新增或更新(精簡掉了一些宏調(diào)用和代碼片段) 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))) { // 數(shù)組元素更新邏輯 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; } // 數(shù)組元素新增邏輯 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 碰撞鏈表維護(hù) CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); if (pDest) { *pDest = p->pData; } // 數(shù)組元素寫入順序維護(hù) 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 中的數(shù)組在新增或修改元素時,首先會根據(jù)給定的 key 計算得到相應(yīng)的 hash 值,然后據(jù)此得到 arBuckets 的索引 nIndex,最終得到鏈表中第一個 Bucket( hash 碰撞鏈表的表頭),即p。
??如果是更新數(shù)組中已有的項,那么會從 p 開始遍歷 hash 碰撞鏈表,直到找到 arkey 與給定的 key 相同的 Bucket,然后更新 pData。
??如果是向數(shù)組中新增項,首先會判斷給定的 key 是否為 interned string 類型,如果是,那么只需要為 Bucket 申請內(nèi)存,然后將 p->arKey 指向給定的 key 的地址即可,否則在為新的 Bucket 申請內(nèi)存的同時還需要為給定的 key 申請內(nèi)存,然后將 p->arKey 指向為 key 申請的內(nèi)存的地址。之后會對新申請的 Bucket 進(jìn)行初始化,最后要做的兩件事:維護(hù) hash 碰撞鏈表和數(shù)組元素寫入順序鏈表。在維護(hù) hash 碰撞的鏈表時,新增的 Bucket 是放在鏈表頭的位置;維護(hù)數(shù)組元素寫入順序的鏈表時,新增的 Bucket 是放在鏈表的末尾,同時將 hashtable 的 pListTail 指向新增的 Bucket。
關(guān)于 PHP 中的 interned string,之前在講解 PHP 7 對字符串處理邏輯優(yōu)化的時候已經(jīng)說明,這里不再贅述
PHP 7
??PHP 7 在 hashtable 的數(shù)據(jù)結(jié)構(gòu)上做了比較大的改動,同時放棄了使用雙向鏈表的方式來維護(hù) hash 碰撞和數(shù)組元素的寫入順序,在內(nèi)存管理以及性能上得到了提升,但理解起來卻不如 PHP 5 中的實現(xiàn)方式直觀。
#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 中數(shù)組添加/修改元素(精簡了部分代碼) 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 的區(qū)別:
??按圖中示例,此時 nNumUsed 的值應(yīng)該為 5,但 nNumOfElements 的值則應(yīng)該為 3。在 PHP 7 中,數(shù)組元素按照寫入順序依次存儲,而 nNumUsed 正好可以用來充當(dāng)數(shù)組元素存儲位置索引的功能。
??另外就是 p = arData + idx ,前面已經(jīng)講過 arData 為 Bucket 類型,這里 +idx 意為指針從 arData 的位置開始向右偏移 idx 個 Bucket 的位置。宏調(diào)用 HT_HASH_EX 也是同樣的道理。
??最后就是 Z_NEXT(p->val),PHP 7 中的 Bucket 結(jié)構(gòu)都內(nèi)嵌了一個 zval,zval 中的聯(lián)合體 u2 中有一項 next 用來記錄hash 碰撞的信息。nIndex 用來標(biāo)識 idx 在映射表中的位置,在往 hashtable 中新增元素時,如果根據(jù)給定的 key 計算得到的 nIndex 的位置已經(jīng)有值(即發(fā)生了 hash 碰撞),那么此時需要將 nIndex 所指向的位置的原值記錄到新增的元素所對應(yīng)的 Bucket 下的 val.u2.next 中。宏調(diào)用 HT_IDX_TO_HASH 的作用是根據(jù) idx 計算得到 Bucket 的以字節(jié)為單位的偏移量。
PHP 5
??在 PHP 5 中,數(shù)組元素的刪除過程中的主要工作是維護(hù) hash 碰撞鏈表和數(shù)組元素寫入順序的鏈表。
// 刪除 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 中數(shù)組在刪除元素時,仍然是先根據(jù)給定的 key 計算 hash,然后找到 arBucket 的 nIndex,最終找到需要刪除的 Bucket 所在的 hash 碰撞的鏈表,通過遍歷鏈表,找到最終需要刪除的 Bucket。
??在實際刪除 Bucket 的過程中,主要做的就是維護(hù)兩個鏈表:hash 碰撞鏈表和數(shù)組元素寫入順序鏈表。再就是釋放內(nèi)存。
PHP 7
??由于 PHP 7 記錄 hash 碰撞信息的方式發(fā)生了變化,所以在刪除元素時處理 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))) { // 如果當(dāng)前 hashtable 的內(nèi)部指針指向了要刪除的 Bucket 或當(dāng)前 hashtable 有遍歷 // 操作,那么需要避開當(dāng)前正在被刪除的 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 在數(shù)組的末尾,則同時回收與 Bucket 相鄰的已經(jīng)被刪除的 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 中數(shù)組元素的刪除,其最終目的是刪除指定的 Bucket。在刪除 Bucket 時還需要處理好 hash 碰撞鏈表維護(hù)的問題。由于 PHP 7 中 hash 碰撞只維護(hù)了一個單向鏈表(通過 Bucket.val.u2.next 來維護(hù)),所以在刪除 Bucket 時還需要找出 hash 碰撞鏈表中的前一項 prev。最后,在刪除 Bucket 時如果當(dāng)前的 hashtable 的內(nèi)部指針(nInternalPointer)正好指向了要刪除的 Bucket 或存在遍歷操作,那么需要改變內(nèi)部指針的指向,同時在遍歷時跳過要刪除的 Bucket。另外需要指出的是,并不是每一次刪除 Bucket 的操作都會回收相應(yīng)的內(nèi)存空間,通常刪除 Bucket 只是將其中 val 的類型標(biāo)記為 IS_UNDEF,只有在擴容或要刪除的 Bucket 為最后一項并且相鄰的 Bucket 為 IS_UNDEF 時才會回收其內(nèi)存空間。
PHP 5
??由于 PHP 5 中有專門用來記錄數(shù)組元素寫入順序的雙向鏈表,所以數(shù)組的遍歷邏輯相對比較簡單。
// 數(shù)組的正向遍歷 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; } // 數(shù)組的反向遍歷 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; }
 ?PHP 5 中 hashtable 的數(shù)據(jù)結(jié)構(gòu)中有三個字段:pInternalPointer 用來記錄數(shù)組遍歷過程中指針指向的當(dāng)前 Bucket 的地址;pListHead 用來記錄保存數(shù)組元素寫入順序的雙向鏈表的表頭;pListTail 用來記錄保存數(shù)組元素寫入順序的雙向鏈表的表尾。數(shù)組的正向遍歷從 pListHead 的位置開始,通過不斷更新 pInternalPointer 來實現(xiàn);反向遍歷從 pListTail 開始,通過不斷更新 pInternalPointer 來實現(xiàn)。
PHP 7
??由于 PHP 7 中數(shù)組的元素是按照寫入的順序存儲,所以遍歷的邏輯相對簡單,只是在遍歷過程中需要跳過被標(biāo)記為 IS_UNDEF 的項。
PHP 5
??前面在談?wù)摂?shù)組元素添加/修改的時候已有提及,每次在數(shù)組新增元素時,都會檢查并處理 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); \ }
??在新增元素時,如果當(dāng)前 arBuckets 的位置沒有其他元素,那么只需要直接寫入新增的 Bucket 即可,否則新增的 Bucket 會被寫入 hash 碰撞雙向鏈表的表頭位置。
PHP 7
??前面已經(jīng)講過,PHP 7 中的 hashtable 是通過 Bucket 中的 val.u2.next 項來維護(hù) hash 碰撞的單向鏈表的。所以,在往 hashtable 中添加新的元素時,最后需要先將 nIndex 位置的值寫入新增的 Bucket 的 val.u2.next 中。而在刪除 Bucket 時,需要同時找出要刪除的 Bucket 所在的 hash 碰撞鏈表中的前一項,以便后續(xù)的 hash 碰撞鏈表的維護(hù)。
PHP 5
??在數(shù)組元素新增/修改的 API 中的最后有一行代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht) 來判斷當(dāng)前 hashtable 是否需要擴容,如果需要則對其進(jìn)行擴容。
// 判斷當(dāng)前 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 中的元素進(jìn)行 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 擴容的前提條件:數(shù)組中元素的數(shù)量超過 hashtable 的 nTableSize 的值。之后,hashtable 的 nTableSize 會翻倍,然后重新為 arBuckets 分配內(nèi)存空間并且更新 nTableMask 的值。最后,由于 nTableMask 發(fā)生變化,需要根據(jù)數(shù)組元素的索引重新計算 nIndex,然后將之前的 Bucket 關(guān)聯(lián)到新分配的 arBuckets 中新的位置。
PHP 7
??在 PHP 7 的新增/修改 hashtable 的 API 中也有判斷是否需要擴容的代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht),當(dāng)滿足條件時則會執(zhí)行擴容操作。
#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)) // 當(dāng) hashtable 的 nNumUsed 大于或等于 nTableSize 時則執(zhí)行擴容操作 #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 中沒有被標(biāo)記為 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 中有被標(biāo)記為 IS_UNDEF 的項 uint32_t old_num_used = ht->nNumUsed; do { if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) { // Bucket 中第一項被標(biāo)記為 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 翻倍,然后進(jìn)行 rehash。在進(jìn)行 rehash 操作時,如果 Bucket 中沒有標(biāo)記為刪除的項(IS_UNDEF),那么 rehash 操作之后 Bucket 的存儲順序不會發(fā)生任何變化,只是 idx 索引存儲的位置會因為 nTableMask 的變化而變化,最終導(dǎo)致 hash 碰撞鏈表的變化。如果 Bucket 中存在被標(biāo)記為刪除的項,那么在 rehash 的過程中會跳過這些 Bucket 項,只保留那些沒有被刪除的項。同時,由于這樣會導(dǎo)致 Bucket 的索引相較于原來發(fā)生變化,所以在 rehash 的過程中需要同時更新 hashtable 內(nèi)部指針的信息以及與遍歷操作相關(guān)的信息。
??在 PHP 7 中,如果一個數(shù)組為索引數(shù)組,并且數(shù)組中的索引為升序排列,那么此時由于 hashtable 中 Bucket 按照寫入順序排列,而數(shù)組索引也是升序的,所以映射表已經(jīng)沒有必要。PHP 7 針對這種特殊的情況對 hashtable 做了一些優(yōu)化 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 的值默認(rèn)為 -2,同時在 hashtable 的 flags 中會進(jìn)行相應(yīng)的標(biāo)記。如果此時 packed hashtable 中沒有任何元素,那么 nTableSize 會設(shè)為 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 的順序不需要做任何調(diào)整,只需要重新分配內(nèi)存空間即可。
需要強調(diào)的是,packed hashtable 只適用于索引為升序排列的索引數(shù)組(索引不一定要連續(xù),中間可以有間隔)。如果索引數(shù)組的索引順序被破壞,或索引中加入了字符串索引,那么此時 packed hashtable 會被轉(zhuǎn)換為普通的 hashtable。
感謝各位的閱讀!關(guān)于“PHP5和PHP7中數(shù)組實現(xiàn)方式有什么不同”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。