&emsp； PHP 5 中 hashtable 的数据结构中有三个字段：pInternalPointer 用来记录数组遍历过程中指针指向的当前 Bucket 的地址；pListHead 用来记录保存数组元素写入顺序的双向链表的表头；pListTail 用来记录保存数组元素写入顺序的双向链表的表尾。数组的正向遍历从 pListHead 的位置开始，通过不断更新 pInternalPointer 来实现；反向遍历从 pListTail 开始，通过不断更新 pInternalPointer 来实现。
PHP 7
由于 PHP 7 中数组的元素是按照写入的顺序存储，所以遍历的逻辑相对简单，只是在遍历过程中需要跳过被标记为 IS_UNDEF 的项。
⒌ hash 碰撞PHP 5
前面在谈论数组元素添加/修改的时候已有提及，每次在数组新增元素时，都会检查并处理 hash 碰撞，即 CONNECT_TO_BUCKET_DLLIST，代码如下
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); #define CONNECT_TO_BUCKET_DLLIST(element, list_head) \ (element)->pNext = (list_head); \ (element)->pLast = NULL; \ if ((element)->pNext) { \ (element)->pNext->pLast = (element); \ }
在新增元素时，如果当前 arBuckets 的位置没有其他元素，那么只需要直接写入新增的 Bucket 即可，否则新增的 Bucket 会被写入 hash 碰撞双向链表的表头位置。
PHP 7
前面已经讲过，PHP 7 中的 hashtable 是通过 Bucket 中的 val.u2.next 项来维护 hash 碰撞的单向链表的。所以，在往 hashtable 中添加新的元素时，最后需要先将 nIndex 位置的值写入新增的 Bucket 的 val.u2.next 中。而在删除 Bucket 时，需要同时找出要删除的 Bucket 所在的 hash 碰撞链表中的前一项，以便后续的 hash 碰撞链表的维护。
⒍ 扩容PHP 5
在数组元素新增/修改的 API 中的最后有一行代码 ZEND_HASH_IF_FULL_DO_RESIZE(ht) 来判断当前 hashtable 是否需要扩容，如果需要则对其进行扩容。
// 判断当前 hashtable 是否需要扩容 #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ if ((ht)->nNumOfElements > (ht)->nTableSize) { \ zend_hash_do_resize(ht); \ } // hashtable 扩容（精简部分代码） ZEND_API int zend_hash_do_resize(HashTable *ht) { Bucket **t; if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */ t = (Bucket **) perealloc(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent); ht->arBuckets = t; ht->nTableSize = (ht->nTableSize << 1); ht->nTableMask = ht->nTableSize - 1; zend_hash_rehash(ht); } } // 扩容后对 hashtable 中的元素进行 rehash（精简部分代码） ZEND_API int zend_hash_rehash(HashTable *ht) { Bucket *p; uint nIndex; if (UNEXPECTED(ht->nNumOfElements == 0)) { return SUCCESS; } memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *)); for (p = ht->pListHead; p != NULL; p = p->pListNext) { nIndex = p->h & ht->nTableMask; CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); ht->arBuckets[nIndex] = p; } return SUCCESS; }
首先，PHP 5 hashtable 扩容的前提条件：数组中元素的数量超过 hashtable 的 nTableSize 的值。之后，hashtable 的 nTableSize 会翻倍，然后重新为 arBuckets 分配内存空间并且更新 nTableMask 的值。最后，由于 nTableMask 发生变化，需要根据数组元素的索引重新计算 nIndex，然后将之前的 Bucket 关联到新分配的 arBuckets 中新的位置。
PHP 7
在 PHP 7 的新增/修改 hashtable 的 API 中也有判断是否需要扩容的代码 ZEND_HASH_IF_FULL_DO_RESIZE(ht)，当满足条件时则会执行扩容操作。
#define HT_SIZE_TO_MASK(nTableSize) \ ((uint32_t)(-((nTableSize) + (nTableSize)))) #define HT_HASH_SIZE(nTableMask) \ (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t)) #define HT_DATA_SIZE(nTableSize) \ ((size_t)(nTableSize) * sizeof(Bucket)) #define HT_SIZE_EX(nTableSize, nTableMask) \ (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask))) #define HT_SET_DATA_ADDR(ht, ptr) do { \ (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \ } while (0) #define HT_GET_DATA_ADDR(ht) \ ((char*)((ht)->arData) - HT_HASH_SIZE((ht)->nTableMask)) // 当 hashtable 的 nNumUsed 大于或等于 nTableSize 时则执行扩容操作 #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ if ((ht)->nNumUsed >= (ht)->nTableSize) { \ zend_hash_do_resize(ht); \ } # define HT_HASH_RESET(ht) \ memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask)) #define HT_IS_WITHOUT_HOLES(ht) \ ((ht)->nNumUsed == (ht)->nNumOfElements) // 扩容（精简部分代码） static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht) { if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */ zend_hash_rehash(ht); } else if (ht->nTableSize < HT_MAX_SIZE) { /* Let's double the table size */ void *new_data, *old_data = HT_GET_DATA_ADDR(ht); uint32_t nSize = ht->nTableSize + ht->nTableSize; Bucket *old_buckets = ht->arData; ht->nTableSize = nSize; new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize); HT_SET_DATA_ADDR(ht, new_data); memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); zend_hash_rehash(ht); } else { zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket)); } } // rehash（精简部分代码） ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht) { Bucket *p; uint32_t nIndex, i; if (UNEXPECTED(ht->nNumOfElements == 0)) { if (!(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { ht->nNumUsed = 0; HT_HASH_RESET(ht); } return SUCCESS; } HT_HASH_RESET(ht); i = 0; p = ht->arData; if (HT_IS_WITHOUT_HOLES(ht)) { // Bucket 中没有被标记为 IS_UNDEF 的项 do { nIndex = p->h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i); p++; } while (++i < ht->nNumUsed); } else { // Bucket 中有被标记为 IS_UNDEF 的项 uint32_t old_num_used = ht->nNumUsed; do { if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) { // Bucket 中第一项被标记为 IS_UNDEF uint32_t j = i; Bucket *q = p; if (EXPECTED(!HT_HAS_ITERATORS(ht))) { // hashtable 没有遍历操作 while (++i < ht->nNumUsed) { p++; if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) { ZVAL_COPY_VALUE(&q->val, &p->val); q->h = p->h; nIndex = q->h | ht->nTableMask; q->key = p->key; Z_NEXT(q->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j); if (UNEXPECTED(ht->nInternalPointer == i)) { ht->nInternalPointer = j; } q++; j++; } } } else { // hashtable 存在遍历操作 uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0); while (++i < ht->nNumUsed) { p++; if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) { ZVAL_COPY_VALUE(&q->val, &p->val); q->h = p->h; nIndex = q->h | ht->nTableMask; q->key = p->key; Z_NEXT(q->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j); if (UNEXPECTED(ht->nInternalPointer == i)) { ht->nInternalPointer = j; } if (UNEXPECTED(i >= iter_pos)) { do { zend_hash_iterators_update(ht, iter_pos, j); iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1); } while (iter_pos < i); } q++; j++; } } } ht->nNumUsed = j; break; } nIndex = p->h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i); p++; } while (++i < ht->nNumUsed); /* Migrate pointer to one past the end of the array to the new one past the end, so that * newly inserted elements are picked up correctly. */ if (UNEXPECTED(HT_HAS_ITERATORS(ht))) { _zend_hash_iterators_update(ht, old_num_used, ht->nNumUsed); } } return SUCCESS; }