Array implementation: PHP5 VS PHP7-PHP Tutorial-php.cn

This article will take you to compare the array implementations of PHP5 and PHP7 and see the differences between them!

Array implementation: PHP5 VS PHP7

From PHP 5 to PHP 7, PHP has greatly improved the memory usage and performance of arrays through modifications to the hashtable data structure and implementation.

⒈ Data structure

// 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;
};

Copy after login

Regardless of other overhead, just look at the space occupied by the Bucket: In PHP 5, considering Memory alignment, a Bucket occupies 72 bytes of space; in PHP 7, a zend_value occupies 8 bytes, and a zval occupies 16 bytes, A Bucket occupies 32 bytes. In comparison, the memory space consumption of Bucket in PHP 7 is more than half lower than that in PHP 5.

The specific memory consumption of PHP 5 arrays has been explained in previous articles, so I won’t go into details here

Now let’s talk about Bucket Storage: In PHP 5, arBucket is a C language array with a length of nTableSize. It stores a pointer to Bucket, and hash# occurs. ## The colliding Bucket is connected in a doubly linked list.

Array implementation: PHP5 VS PHP7 ## In PHP 7,

Bucket

is stored in the order in which the array elements are written, and its index value is idx, which Values are stored in the mapped area to the left of *arData. idx The index in the mapping area is nIndex, the nIndex value is a negative number, determined by the hash of the array key The value is ORed with 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);

Copy after login

It needs to be pointed out here that the reason why

nTableMask

is set to twice the nTableSize is to calculate nIndex can reduce the probability of hash collision.

⒉ Add/modify elements

##PHP 5

First Let’s talk about adding and modifying array elements in PHP 5. Since the insertion order and hash collision of array elements in PHP 5 are maintained through a doubly linked list, although it is a bit complicated to implement, it is relatively easy to understand.

// 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;
}

Copy after login

When adding or modifying elements to an array in PHP 5, the corresponding hash value will first be calculated based on the given

key

, and then

arBuckets## will be obtained accordingly. The index nIndex of # finally gets the first Bucket in the linked list (hash collides with the header of the linked list), which is p. If you are updating an existing item in the array, then the hash collision linked list will be traversed starting from

# until you find arkey# that matches the given The key of the same Bucket, and then update pData. If an item is added to the array, it will first be judged whether the given key is of type

interned string

#. If so, then it only needs to be Bucket applies for memory, and then points p->arKey to the address of the given key, otherwise apply for memory for the new Bucket At the same time, you also need to apply for memory for the given key, and then point p->arKey to the address of the memory requested for key. Afterwards, the newly applied Bucket will be initialized, and the last two things to do are to maintain the hash collision linked list and the array element writing sequence linked list. When maintaining the linked list of hash collision, the newly added Bucket is placed at the head of the linked list; when maintaining the linked list of the writing order of array elements, the newly added Bucket is placed at the end of the linked list, and # The pListTail of ##hashtable points to the newly added Bucket. Regarding the interned string in PHP, it has been explained before when explaining the optimization of string processing logic in PHP 7, so I won’t go into details here

PHP 7

PHP 7 has made major changes in the data structure of hashtable, and at the same time abandoned the use of doubly linked lists to maintain

Collision and the writing order of array elements have been improved in memory management and performance, but it is not as intuitive to understand as the implementation in 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;
}

Copy after login

Here we need to explain the difference between nNumUsed and nNumOfElements

<p> 按图中示例，此时 <code>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;
}

Copy after login

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);
}

Copy after login

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;
}

Copy after login

&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);                \
    }

Copy after login

在新增元素时，如果当前 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&#39;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;
}

Copy after login

首先，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&#39;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;
}

Copy after login

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&#39;t overwrite iterator count. */
    ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
    HT_HASH_RESET_PACKED(ht);
}

Copy after login

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));
}

Copy after login

另外，packed hashtable 在扩容时，只需要将 nTableSize 翻倍，同时由于索引是升序排列的，所以 Bucket 的顺序不需要做任何调整，只需要重新分配内存空间即可。

需要强调的是，packed hashtable 只适用于索引为升序排列的索引数组（索引不一定要连续，中间可以有间隔）。如果索引数组的索引顺序被破坏，或索引中加入了字符串索引，那么此时 packed hashtable 会被转换为普通的 hashtable。

推荐学习：《PHP视频教程》

The above is the detailed content of Array implementation: PHP5 VS PHP7. For more information, please follow other related articles on the PHP Chinese website!