⒈ 数据结构
⒉ 添加/修改元素
⒊ 删除元素
⒋ 数组遍历
⒌ hash 碰撞
⒍ 扩容
⒎ PHP 7 中的 packed hashtable
总结
从 PHP 5 到 PHP 7 ，PHP 通过对 hashtable 数据结构和实现方式的修改，使得数组在内存占用和性能上有了很大的提升。

⒈ 数据结构
// 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;

  1. typedef struct _hashtable {
  2.     uint nTableSize; /*当前 ht 所分配的 bucket 的总数，2^n*/
  3.     uint nTableMask; /*nTableSize - 1，用于计算索引*/
  4.     uint nNumOfElements; /*实际存储的元素的数量*/
  5.     ulong nNextFreeElement; /*下一个可以被使用的整数 key*/
  6.     Bucket *pInternalPointer; /*数组遍历时，记录当前 bucket 的地址*/
  7.     Bucket *pListHead;
  8.     Bucket *pListTail;
  9.     Bucket **arBuckets; /*记录 bucket 的 C 语言数组*/
  10.     dtor_func_t pDestructor; /*删除数组元素时内部调用的函数*/
  11.     zend_bool persistent; /*标识 ht 是否永久有效*/
  12.     unsigned char nApplyCount; /*ht 允许的最大递归深度*/
  13.     zend_bool bApplyProtection; /*是否启用递归保护*/
  14. #if ZEND_DEBUG
  15.     int inconsistent;
  16. #endif
  17. } HashTable;
  19. // PHP 7 中 hashtable 的数据结构
  20. // PHP 7 中个子版本以及阶段版本中对 hashtable 的数据结构的定义会有微小的差别，这里使用的是 PHP 7.4.0 中的定义
  21. struct _zend_string {
  22.     zend_refcounted_h gc;
  23.     zend_ulong        h;  /*字符串 key 的 hash 值*/
  24.     size_t            len;  /*字符串 key 的长度*/
  25.     char              val[1]; /*存储字符串的值，利用了 struct hack*/
  26. };
  28. typedef struct _Bucket {
  29.     zval              val;  /*内嵌 zval 结构，存储数组的 value 值*/
  30.     zend_ulong        h;                /* hash value (or numeric index)   */
  31.     zend_string      *key;              /* string key or NULL for numerics */
  32. } Bucket;
  34. typedef struct _zend_array HashTable;
  36. struct _zend_array {
  37.     zend_refcounted_h gc;
  38.     union {
  39.         struct {
  40.             ZEND_ENDIAN_LOHI_4(
  41.                 zend_uchar    flags,
  42.                 zend_uchar    _unused,
  43.                 zend_uchar    nIteratorsCount,
  44.                 zend_uchar    _unused2)
  45.         } v;
  46.         uint32_t flags;
  47.     } u;
  48.     uint32_t          nTableMask; /*作用与 PHP 5 中 hashtable 中 nTableMask 作用相同，但实现逻辑稍有变化*/
  49.     Bucket           *arData; /*存储 bucket 相关的信息*/
  50.     uint32_t          nNumUsed; /*ht 中已经使用的 bucket 的数量，在 nNumOfElements 的基础上加上删除的 key*/
  51.     uint32_t          nNumOfElements;
  52.     uint32_t          nTableSize;
  53.     uint32_t          nInternalPointer;
  54.     zend_long         nNextFreeElement;
  55.     dtor_func_t       pDestructor;
  56. };

不考虑其他开销，单从 Bucket 所占用的空间来看：在 PHP 5 中，考虑到内存对齐，一个 Bucket 占用的空间为 72 字节；在 PHP 7 中，一个 zend_value 占 8 字节，一个 zval 占 16 字节，一个 Bucket 占 32 字节。相比之下，PHP 7 中 Bucket 的内存空间消耗比 PHP 5 低了一半以上。

具体 PHP 5 数组的内存消耗情况，之前的文章已有讲解，这里不再赘述

  现在来谈谈 Bucket 的存储：在 PHP 5 中，arBucket 是一个 C 语言数组，长度为 nTableSize，存储的是指向 Bucket 的指针，发生 hash 碰撞的 Bucket 以双向链表的方式连接。

  在 PHP 7 中，Bucket 按照数组元素写入的顺序依次存储，其索引值为 idx，该值存储在 *arData 左侧的映射区域中。idx 在映射区域中的索引为 nIndex，nIndex 值为负数，由数组 key 的 hash 值与 nTableMask 进行或运算得到。

  1. // nTableMask 为 -2 倍的 nTableSize 的无符号表示
  2. #define HT_SIZE_TO_MASK(nTableSize) \
  3.     ((uint32_t)(-((nTableSize) + (nTableSize))))
  5. // 在通过 idx 查找 Bucket 时，data 默认为 Bucket 类型，加 idx 表示向右偏移 idx 个 Bucket 位置
  6. # define HT_HASH_TO_BUCKET_EX(data, idx) \
  7.     ((data) + (idx))
  9. // 在通过 nIndex 查找 idx 时，
  10. // (uint32_t*)(data) 首先将 data 转换成了 uint32_t* 类型的数组
  11. // 然后将 nIndex 转换成有符号数（负数），然后以数组的方式查找 idx 的值
  12. #define HT_HASH_EX(data, idx) \
  13.     ((uint32_t*)(data))[(int32_t)(idx)]
  15. nIndex = h | ht->nTableMask;
  16. idx = HT_HASH_EX(arData, nIndex);
  17. p = HT_HASH_TO_BUCKET_EX(arData, idx);

 这里需要指出，nTableMask 之所以设置为 nTableSize 的两倍，是这样在计算 nIndex 时可以减小 hash 碰撞的概率。

⒉ 添加/修改元素
PHP 5

  先来谈谈 PHP 5 中数组元素的添加和修改，由于 PHP 5 中数组元素的插入顺序以及 hash 碰撞都是通过双向链表的方式来维护，所以虽然实现起来有些复杂，但理解起来相对容易一些。
// hash 碰撞双向链表的维护

  1. #define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
  2.     (element)->pNext = (list_head);                         \
  3.     (element)->pLast = NULL;                                \
  4.     if ((element)->pNext) {                                 \
  5.         (element)->pNext->pLast = (element);                \
  6.     }
  8. #define CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, last, next)\
  9.     (element)->pListLast = (last);                          \
  10.     (element)->pListNext = (next);                          \
  11.     if ((last) != NULL) {                                   \
  12.         (last)->pListNext = (element);                      \
  13.     } else {                                                \
  14.         (ht)->pListHead = (element);                        \
  15.     }                                                       \
  16.     if ((next) != NULL) {                                   \
  17.         (next)->pListLast = (element);                      \
  18.     } else {                                                \
  19.         (ht)->pListTail = (element);                        \
  20.     }                                                       \
  21. // 数组元素插入顺序双向链表的维护
  22. #define CONNECT_TO_GLOBAL_DLLIST(element, ht)                                   \
  23.     CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, (ht)->pListTail, (Bucket *) NULL); \
  24.     if ((ht)->pInternalPointer == NULL) {                                       \
  25.         (ht)->pInternalPointer = (element);                                     \
  26.     }
  27. // 数组元素的更新
  28. #define UPDATE_DATA(ht, p, pData, nDataSize)                                            \
  29.     if (nDataSize == sizeof(void*)) {                                                   \
  30.         // 值为指针类型的元素的更新                                                         \
  31.         if ((p)->pData != &(p)->pDataPtr) {                                             \
  32.             pefree_rel((p)->pData, (ht)->persistent);                                   \
  33.         }                                                                               \
  34.         // pDataPtr 存储元素值的地址，pData 存储 pDataPtr 的地址                             \
  35.         memcpy(&(p)->pDataPtr, pData, sizeof(void *));                                  \
  36.         (p)->pData = &(p)->pDataPtr;                                                    \
  37.     } else {                                                                            \
  38.         // 如果数组元素为值类型，则存入 pData，此时 pDataPtr 为 Null                          \
  39.         if ((p)->pData == &(p)->pDataPtr) {                                             \
  40.             (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);            \
  41.             (p)->pDataPtr=NULL;                                                         \
  42.         } else {                                                                        \
  43.             (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);   \
  44.             /* (p)->pDataPtr is already NULL so no need to initialize it */             \
  45.         }                                                                               \
  46.         memcpy((p)->pData, pData, nDataSize);                                           \
  47.     }
  48. // 数组元素的初始化
  49. #define INIT_DATA(ht, p, _pData, nDataSize);                                \
  50.     if (nDataSize == sizeof(void*)) {                                   \
  51.         // 指针类型元素的初始化                                            \
  52.         memcpy(&(p)->pDataPtr, (_pData), sizeof(void *));                   \
  53.         (p)->pData = &(p)->pDataPtr;                                    \
  54.     } else {                                                            \
  55.         // 值类型元素的初始化                                                \
  56.         (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
  57.         memcpy((p)->pData, (_pData), nDataSize);                            \
  58.         (p)->pDataPtr=NULL;                                             \
  59.     }
  60. // hashtable 初始化校验，如果没有初始化，则初始化 hashtable
  61. #define CHECK_INIT(ht) do {                                             \
  62.     if (UNEXPECTED((ht)->nTableMask == 0)) {                                \
  63.         (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);   \
  64.         (ht)->nTableMask = (ht)->nTableSize - 1;                        \
  65.     }                                                                   \
  66. } while (0)
  67. // 数组元素的新增或更新（精简掉了一些宏调用和代码片段)
  68. 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)
  69. {
  70.     ulong h;
  71.     uint nIndex;
  72.     Bucket *p;
  74.     CHECK_INIT(ht);
  76.     h = zend_inline_hash_func(arKey, nKeyLength);
  77.     nIndex = h & ht->nTableMask;
  79.     p = ht->arBuckets[nIndex];
  80.     while (p != NULL) {
  81.         if (p->arKey == arKey ||
  82.             ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
  83.                 // 数组元素更新逻辑
  84.                 if (flag & HASH_ADD) {
  85.                     return FAILURE;
  86.                 }
  87.                 ZEND_ASSERT(p->pData != pData);
  88.                 if (ht->pDestructor) {
  89.                     ht->pDestructor(p->pData);
  90.                 }
  91.                 UPDATE_DATA(ht, p, pData, nDataSize);
  92.                 if (pDest) {
  93.                     *pDest = p->pData;
  94.                 }
  95.                 return SUCCESS;
  96.         }
  97.         p = p->pNext;
  98.     }
  99.     // 数组元素新增逻辑
  100.     if (IS_INTERNED(arKey)) {
  101.         p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
  102.         p->arKey = arKey;
  103.     } else {
  104.         p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
  105.         p->arKey = (const char*)(p + 1);
  106.         memcpy((char*)p->arKey, arKey, nKeyLength);
  107.     }
  108.     p->nKeyLength = nKeyLength;
  109.     INIT_DATA(ht, p, pData, nDataSize);
  110.     p->h = h;
  111.     // hash 碰撞链表维护
  112.     CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
  113.     if (pDest) {
  114.         *pDest = p->pData;
  115.     }
  116.     // 数组元素写入顺序维护
  117.     CONNECT_TO_GLOBAL_DLLIST(p, ht);
  118.     ht->arBuckets[nIndex] = p;
  120.     ht->nNumOfElements++;
  121.     ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
  122.     return SUCCESS;
  123. }

 PHP 5 中的数组在新增或修改元素时，首先会根据给定的 key 计算得到相应的 hash 值，然后据此得到 arBuckets 的索引 nIndex，最终得到链表中第一个 Bucket（ hash 碰撞链表的表头），即p。

  如果是更新数组中已有的项，那么会从 p 开始遍历 hash 碰撞链表，直到找到 arkey 与给定的 key 相同的 Bucket，然后更新 pData。

 如果是向数组中新增项，首先会判断给定的 key 是否为 interned string 类型，如果是，那么只需要为 Bucket 申请内存，然后将 p->arKey 指向给定的 key 的地址即可，否则在为新的 Bucket 申请内存的同时还需要为给定的 key 申请内存，然后将 p->arKey 指向为 key 申请的内存的地址。之后会对新申请的 Bucket 进行初始化，最后要做的两件事：维护 hash 碰撞链表和数组元素写入顺序链表。在维护 hash 碰撞的链表时，新增的 Bucket 是放在链表头的位置；维护数组元素写入顺序的链表时，新增的 Bucket 是放在链表的末尾，同时将 hashtable 的 pListTail 指向新增的 Bucket。

关于 PHP 中的 interned string，之前在讲解 PHP 7 对字符串处理逻辑优化的时候已经说明，这里不再赘述

PHP 7

  PHP 7 在 hashtable 的数据结构上做了比较大的改动，同时放弃了使用双向链表的方式来维护 hash 碰撞和数组元素的写入顺序，在内存管理以及性能上得到了提升，但理解起来却不如 PHP 5 中的实现方式直观。

  1.   #define Z_NEXT(zval)                (zval).u2.next
  2. #define HT_HASH_EX(data, idx) \
  3.     ((uint32_t*)(data))[(int32_t)(idx)]
  4. # define HT_IDX_TO_HASH(idx) \
  5.     ((idx) * sizeof(Bucket))
  7. // PHP 7 中数组添加/修改元素（精简了部分代码）
  8. static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag)
  9. {
  10.     zend_ulong h;
  11.     uint32_t nIndex;
  12.     uint32_t idx;
  13.     Bucket *p, *arData;
  15.     /*... ...*/
  17.     ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
  19. add_to_hash:
  20.     idx = ht->nNumUsed++;
  21.     ht->nNumOfElements++;
  22.     arData = ht->arData;
  23.     p = arData + idx;
  24.     p->key = key;
  25.     p->h = h = ZSTR_H(key);
  26.     nIndex = h | ht->nTableMask;
  27.     Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
  28.     HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
  29.     ZVAL_COPY_VALUE(&p->val, pData);
  31.     return &p->val;
  32. }

这里需要先说明一下 nNumUsed 和 nNumOfElements 的区别：

  按图中示例，此时 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 碰撞链表和数组元素写入顺序的链表。

  1. static zend_always_inline void i_zend_hash_bucket_delete(HashTable *ht, Bucket *p)
  2. {
  3.     if (p->pLast) {
  4.         p->pLast->pNext = p->pNext;
  5.     } else {
  6.         ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
  7.     }
  8.     if (p->pNext) {
  9.         p->pNext->pLast = p->pLast;
  10.     }
  11.     if (p->pListLast != NULL) {
  12.         p->pListLast->pListNext = p->pListNext;
  13.     } else {
  14.         /* Deleting the head of the list */
  15.         ht->pListHead = p->pListNext;
  16.     }
  17.     if (p->pListNext != NULL) {
  18.         p->pListNext->pListLast = p->pListLast;
  19.     } else {
  20.         /* Deleting the tail of the list */
  21.         ht->pListTail = p->pListLast;
  22.     }
  23.     if (ht->pInternalPointer == p) {
  24.         ht->pInternalPointer = p->pListNext;
  25.     }
  26.     ht->nNumOfElements--;
  27.     if (ht->pDestructor) {
  28.         ht->pDestructor(p->pData);
  29.     }
  30.     if (p->pData != &p->pDataPtr) {
  31.         pefree(p->pData, ht->persistent);
  32.     }
  33.     pefree(p, ht->persistent);
  34. }
  35. // 元素删除
  36. ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
  37. {
  38.     uint nIndex;
  39.     Bucket *p;
  41.     if (flag == HASH_DEL_KEY) {
  42.         h = zend_inline_hash_func(arKey, nKeyLength);
  43.     }
  44.     nIndex = h & ht->nTableMask;
  46.     p = ht->arBuckets[nIndex];
  47.     while (p != NULL) {
  48.         if ((p->h == h)
  49.              && (p->nKeyLength == nKeyLength)
  50.              && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
  51.                  || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
  52.             i_zend_hash_bucket_delete(ht, p);
  53.             return SUCCESS;
  54.         }
  55.         p = p->pNext;
  56.     }
  57.     return FAILURE;
  58. }

 PHP 5 中数组在删除元素时，仍然是先根据给定的 key 计算 hash，然后找到 arBucket 的 nIndex，最终找到需要删除的 Bucket 所在的 hash 碰撞的链表，通过遍历链表，找到最终需要删除的 Bucket。

  在实际删除 Bucket 的过程中，主要做的就是维护两个链表：hash 碰撞链表和数组元素写入顺序链表。再就是释放内存。

PHP 7

  由于 PHP 7 记录 hash 碰撞信息的方式发生了变化，所以在删除元素时处理 hash 碰撞链表的逻辑也会有所不同。另外，在删除元素时，还有可能会遇到空间回收的情况。

  1. #define IS_UNDEF                    0
  2. #define Z_TYPE_INFO(zval)           (zval).u1.type_info
  3. #define Z_TYPE_INFO_P(zval_p)       Z_TYPE_INFO(*(zval_p))
  4. #define ZVAL_UNDEF(z) do {              \
  5.         Z_TYPE_INFO_P(z) = IS_UNDEF;    \
  6.     } while (0)
  8. static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
  9. {
  10.     // 从 hash 碰撞链表中删除指定的 Bucket
  11.     if (!(HT_FLAGS(ht) & HASH_FLAG_PACKED)) {
  12.         if (prev) {
  13.             Z_NEXT(prev->val) = Z_NEXT(p->val);
  14.         } else {
  15.             HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);
  16.         }
  17.     }
  18.     idx = HT_HASH_TO_IDX(idx);
  19.     ht->nNumOfElements--;
  20.     if (ht->nInternalPointer == idx || UNEXPECTED(HT_HAS_ITERATORS(ht))) {
  21.         // 如果当前 hashtable 的内部指针指向了要删除的 Bucket 或当前 hashtable 有遍历
  22.         // 操作，那么需要避开当前正在被删除的 Bucket
  23.         uint32_t new_idx;
  25.         new_idx = idx;
  26.         while (1) {
  27.             new_idx++;
  28.             if (new_idx >= ht->nNumUsed) {
  29.                 break;
  30.             } else if (Z_TYPE(ht->arData[new_idx].val) != IS_UNDEF) {
  31.                 break;
  32.             }
  33.         }
  34.         if (ht->nInternalPointer == idx) {
  35.             ht->nInternalPointer = new_idx;
  36.         }
  37.         zend_hash_iterators_update(ht, idx, new_idx);
  38.     }
  39.     if (ht->nNumUsed - 1 == idx) {
  40.         //如果被删除的 Bucket 在数组的末尾，则同时回收与 Bucket 相邻的已经被删除的 Bucket 的空间
  41.         do {
  42.             ht->nNumUsed--;
  43.         } while (ht->nNumUsed > 0 && (UNEXPECTED(Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)));
  44.         ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed);
  45.     }
  46.     if (p->key) {
  47.         // 删除 string 类型的索引
  48.         zend_string_release(p->key);
  49.     }
  50.     // 删除 Bucket
  51.     if (ht->pDestructor) {
  52.         zval tmp;
  53.         ZVAL_COPY_VALUE(&tmp, &p->val);
  54.         ZVAL_UNDEF(&p->val);
  55.         ht->pDestructor(&tmp);
  56.     } else {
  57.         ZVAL_UNDEF(&p->val);
  58.     }
  59. }
  61. static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint32_t idx, Bucket *p)
  62. {
  63.     Bucket *prev = NULL;
  65.     if (!(HT_FLAGS(ht) & HASH_FLAG_PACKED)) {
  66.         // 如果被删除的 Bucket 存在 hash 碰撞的情况，那么需要找出其在 hash 碰撞链表中的位置
  67.         uint32_t nIndex = p->h | ht->nTableMask;
  68.         uint32_t i = HT_HASH(ht, nIndex);
  70.         if (i != idx) {
  71.             prev = HT_HASH_TO_BUCKET(ht, i);
  72.             while (Z_NEXT(prev->val) != idx) {
  73.                 i = Z_NEXT(prev->val);
  74.                 prev = HT_HASH_TO_BUCKET(ht, i);
  75.             }
  76.         }
  77.     }
  79.     _zend_hash_del_el_ex(ht, idx, p, prev);
  80. }
  82. ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p)
  83. {
  84.     IS_CONSISTENT(ht);
  85.     HT_ASSERT_RC1(ht);
  86.     _zend_hash_del_el(ht, HT_IDX_TO_HASH(p - ht->arData), p);
  87. }

 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;

  1.     IS_CONSISTENT(ht);
  3.     if (*current) {
  4.         *current = (*current)->pListNext;
  5.         return SUCCESS;
  6.     } else
  7.         return FAILURE;
  8. }
  9. // 数组的反向遍历
  10. ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
  11. {
  12.     HashPosition *current = pos ? pos : &ht->pInternalPointer;
  14.     IS_CONSISTENT(ht);
  16.     if (*current) {
  17.         *current = (*current)->pListLast;
  18.         return SUCCESS;
  19.     } else
  20.         return FAILURE;
  21. }

&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]);

  1. #define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
  2.     (element)->pNext = (list_head);                         \
  3.     (element)->pLast = NULL;                                \
  4.     if ((element)->pNext) {                                 \
  5.         (element)->pNext->pLast = (element);                \
  6.     }

 在新增元素时，如果当前 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 是否需要扩容，如果需要则对其进行扩容。

  1. #define ZEND_HASH_IF_FULL_DO_RESIZE(ht)             \
  2.     if ((ht)->nNumOfElements > (ht)->nTableSize) {  \
  3.         zend_hash_do_resize(ht);                    \
  4.     }
  5. // hashtable 扩容（精简部分代码）
  6. ZEND_API int zend_hash_do_resize(HashTable *ht)
  7. {
  8.     Bucket **t;
  10.     if ((ht->nTableSize << 1) > 0) {    /* Let's double the table size */
  11.         t = (Bucket **) perealloc(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
  12.         ht->arBuckets = t;
  13.         ht->nTableSize = (ht->nTableSize << 1);
  14.         ht->nTableMask = ht->nTableSize - 1;
  15.         zend_hash_rehash(ht);
  16.     }
  17. }
  18. // 扩容后对 hashtable 中的元素进行 rehash（精简部分代码）
  19. ZEND_API int zend_hash_rehash(HashTable *ht)
  20. {
  21.     Bucket *p;
  22.     uint nIndex;
  24.     if (UNEXPECTED(ht->nNumOfElements == 0)) {
  25.         return SUCCESS;
  26.     }
  28.     memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
  29.     for (p = ht->pListHead; p != NULL; p = p->pListNext) {
  30.         nIndex = p->h & ht->nTableMask;
  31.         CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
  32.         ht->arBuckets[nIndex] = p;
  33.     }
  34.     return SUCCESS;
  35. }

首先，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)，当满足条件时则会执行扩容操作

  1. #define HT_SIZE_TO_MASK(nTableSize) \
  2.     ((uint32_t)(-((nTableSize) + (nTableSize))))
  3. #define HT_HASH_SIZE(nTableMask) \
  4.     (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
  5. #define HT_DATA_SIZE(nTableSize) \
  6.     ((size_t)(nTableSize) * sizeof(Bucket))
  7. #define HT_SIZE_EX(nTableSize, nTableMask) \
  8.     (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask)))
  10. #define HT_SET_DATA_ADDR(ht, ptr) do { \
  11.         (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
  12.     } while (0)
  13. #define HT_GET_DATA_ADDR(ht) \
  14.     ((char*)((ht)->arData) - HT_HASH_SIZE((ht)->nTableMask))
  15. // 当 hashtable 的 nNumUsed 大于或等于 nTableSize 时则执行扩容操作
  16. #define ZEND_HASH_IF_FULL_DO_RESIZE(ht)             \
  17.     if ((ht)->nNumUsed >= (ht)->nTableSize) {       \
  18.         zend_hash_do_resize(ht);                    \
  19.     }
  21. # define HT_HASH_RESET(ht) \
  22.     memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))
  24. #define HT_IS_WITHOUT_HOLES(ht) \
  25.     ((ht)->nNumUsed == (ht)->nNumOfElements)
  26. // 扩容（精简部分代码）
  27. static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
  28. {
  29.     if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
  30.         zend_hash_rehash(ht);
  31.     } else if (ht->nTableSize < HT_MAX_SIZE) {  /* Let's double the table size */
  32.         void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
  33.         uint32_t nSize = ht->nTableSize + ht->nTableSize;
  34.         Bucket *old_buckets = ht->arData;
  36.         ht->nTableSize = nSize;
  37.         new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
  38.         ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize);
  39.         HT_SET_DATA_ADDR(ht, new_data);
  40.         memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
  41.         pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
  42.         zend_hash_rehash(ht);
  43.     } else {
  44.         zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
  45.     }
  46. }
  47. // rehash（精简部分代码）
  48. ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
  49. {
  50.     Bucket *p;
  51.     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;
}

  1.     HT_HASH_RESET(ht);
  2.     i = 0;
  3.     p = ht->arData;
  4.     if (HT_IS_WITHOUT_HOLES(ht)) {
  5.     // Bucket 中没有被标记为 IS_UNDEF 的项
  6.         do {
  7.             nIndex = p->h | ht->nTableMask;
  8.             Z_NEXT(p->val) = HT_HASH(ht, nIndex);
  9.             HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
  10.             p++;
  11.         } while (++i < ht->nNumUsed);
  12.     } else {
  13.     // Bucket 中有被标记为 IS_UNDEF 的项
  14.         uint32_t old_num_used = ht->nNumUsed;
  15.         do {
  16.             if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
  17.             // Bucket 中第一项被标记为 IS_UNDEF
  18.                 uint32_t j = i;
  19.                 Bucket *q = p;
  21.                 if (EXPECTED(!HT_HAS_ITERATORS(ht))) {
  22.                 // hashtable 没有遍历操作
  23.                     while (++i < ht->nNumUsed) {
  24.                         p++;
  25.                         if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
  26.                             ZVAL_COPY_VALUE(&q->val, &p->val);
  27.                             q->h = p->h;
  28.                             nIndex = q->h | ht->nTableMask;
  29.                             q->key = p->key;
  30.                             Z_NEXT(q->val) = HT_HASH(ht, nIndex);
  31.                             HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
  32.                             if (UNEXPECTED(ht->nInternalPointer == i)) {
  33.                                 ht->nInternalPointer = j;
  34.                             }
  35.                             q++;
  36.                             j++;
  37.                         }
  38.                     }
  39.                 } else {
  40.                 // hashtable 存在遍历操作
  41.                     uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0);
  43.                     while (++i < ht->nNumUsed) {
  44.                         p++;
  45.                         if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
  46.                             ZVAL_COPY_VALUE(&q->val, &p->val);
  47.                             q->h = p->h;
  48.                             nIndex = q->h | ht->nTableMask;
  49.                             q->key = p->key;
  50.                             Z_NEXT(q->val) = HT_HASH(ht, nIndex);
  51.                             HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
  52.                             if (UNEXPECTED(ht->nInternalPointer == i)) {
  53.                                 ht->nInternalPointer = j;
  54.                             }
  55.                             if (UNEXPECTED(i >= iter_pos)) {
  56.                                 do {
  57.                                     zend_hash_iterators_update(ht, iter_pos, j);
  58.                                     iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
  59.                                 } while (iter_pos < i);
  60.                             }
  61.                             q++;
  62.                             j++;
  63.                         }
  64.                     }
  65.                 }
  66.                 ht->nNumUsed = j;
  67.                 break;
  68.             }
  69.             nIndex = p->h | ht->nTableMask;
  70.             Z_NEXT(p->val) = HT_HASH(ht, nIndex);
  71.             HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
  72.             p++;
  73.         } while (++i < ht->nNumUsed);
  75.         /* Migrate pointer to one past the end of the array to the new one past the end, so that
  76.          * newly inserted elements are picked up correctly. */
  77.         if (UNEXPECTED(HT_HAS_ITERATORS(ht))) {
  78.             _zend_hash_iterators_update(ht, old_num_used, ht->nNumUsed);
  79.         }
  80.     }
  81.     return SUCCESS;
  82. }

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

  1. #define HT_MIN_MASK ((uint32_t) -2)
  2. #define HT_MIN_SIZE 8
  4. #define HT_HASH_RESET_PACKED(ht) do { \
  5.         HT_HASH(ht, -2) = HT_INVALID_IDX; \
  6.         HT_HASH(ht, -1) = HT_INVALID_IDX; \
  7.     } while (0)
  9. static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht)
  10. {
  11.     void *data;
  13.     if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) {
  14.         data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), 1);
  15.     } else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) {
  16.         data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
  17.     } else {
  18.         data = emalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK));
  19.     }
  20.     HT_SET_DATA_ADDR(ht, data);
  21.     /* Don't overwrite iterator count. */
  22.     ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
  23.     HT_HASH_RESET_PACKED(ht);
  24. }

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。

总结

更多相关文章

  1. js语法：解构赋值、dom元素的增删改、dataset,classList对象的使用
  2. 解构赋值、DOM操作以及dataset和classList对象的使用
  3. 模态框与flex,grid思维导图
  4. PHP获取数组中单列值的方法
  5. HTML伪类、盒子模型学习与应用
  6. box-sizing的作用+伪类选择器的参数 an+b 的应用+媒体查询：@media
  7. 盒模型，伪类与媒体查询
  8. 1.box-sizing属性 2.伪类选择器 3.媒体查询
  9. CSS Position(定位)详解

随机推荐

  1. android点击邮箱链接跳转发送
  2. Android 深入解析selector
  3. Android ScrollView 判断到顶到底，和设置
  4. Android：开发常用的名令集锦
  5. Android Touch事件分发机制学习
  6. Android隐式启动Activity匹配详解：Action，c
  7. Android TextView文字过多，添加滚动条
  8. Windows下载Android全部源码
  9. 解决CardView无点击效果 实现水波纹效果
  10. android sdk setup时呈现:Failed to fetc