Array implementation: PHP5 VS PHP7

  另外就是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 5hashtable扩容的前提条件：数组中元素的数量超过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。

推荐学习：《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!