目錄
- ⒈ 數(shù)據(jù)結(jié)構(gòu)
- ⒉ 添加/修改元素
- ⒊ 刪除元素
- ⒋ 數(shù)組遍歷
- ⒌ hash 碰撞
- ⒍ 擴容
- ⒎ PHP 7 中的 packed hashtable
- 總結(jié)
從 PHP 5 到 PHP 7 ，PHP 通過對 hashtable 數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)方式的修改，使得數(shù)組在內(nèi)存占用和性能上有了很大的提升。
⒈ 數(shù)據(jù)結(jié)構(gòu)
// 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; /*是否啟用遞歸保護*/
#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 進行或運算得到。
// 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 碰撞都是通過雙向鏈表的方式來維護，所以雖然實現(xiàn)起來有些復(fù)雜，但理解起來相對容易一些。
// 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); \
} \
// 數(shù)組元素插入順序雙向鏈表的維護
#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 碰撞鏈表維護
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
if (pDest) {
*pDest = p->pData;
}
// 數(shù)組元素寫入順序維護
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 進行初始化，最后要做的兩件事：維護 hash 碰撞鏈表和數(shù)組元素寫入順序鏈表。在維護 hash 碰撞的鏈表時，新增的 Bucket 是放在鏈表頭的位置；維護數(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)上做了比較大的改動，同時放棄了使用雙向鏈表的方式來維護 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ù)組元素的刪除過程中的主要工作是維護 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 的過程中，主要做的就是維護兩個鏈表：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 碰撞鏈表維護的問題。由于 PHP 7 中 hash 碰撞只維護了一個單向鏈表（通過 Bucket.val.u2.next 來維護），所以在刪除 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)存空間。
⒋ 數(shù)組遍歷
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;
}
emsp； 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 的項。
⒌ hash 碰撞
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 項來維護 hash 碰撞的單向鏈表的。所以，在往 hashtable 中添加新的元素時，最后需要先將 nIndex 位置的值寫入新增的 Bucket 的 val.u2.next 中。而在刪除 Bucket 時，需要同時找出要刪除的 Bucket 所在的 hash 碰撞鏈表中的前一項，以便后續(xù)的 hash 碰撞鏈表的維護。
⒍ 擴容
PHP 5
在數(shù)組元素新增/修改的 API 中的最后有一行代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht) 來判斷當(dāng)前 hashtable 是否需要擴容，如果需要則對其進行擴容。
// 判斷當(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 中的元素進行 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 翻倍，然后進行 rehash。在進行 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 中的 packed hashtable
在 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 中會進行相應(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。
總結(jié)
到此這篇關(guān)于PHP5和PHP7中數(shù)組實現(xiàn)方式比較的文章就介紹到這了,更多相關(guān)PHP5和PHP7數(shù)組實現(xiàn)比較內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- PHP7.1方括號數(shù)組符號多值復(fù)制及指定鍵值賦值用法分析
- PHP7常量數(shù)組用法分析
- PHP7數(shù)組的底層實現(xiàn)示例
- php5.5新數(shù)組函數(shù)array_column使用
