Implémentation du tableau : PHP5 VS PHP7-tutoriel php-php.cn

Cet article vous amènera à comparer les implémentations de tableaux de PHP5 et PHP7 et à voir les différences entre elles !

Implémentation du tableau : PHP5 VS PHP7

De PHP 5 à PHP 7, PHP a considérablement amélioré l'utilisation de la mémoire et les performances des tableaux grâce à des modifications de la structure et de l'implémentation des données de la table de hachage.

⒈ Structure des données

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

Copier après la connexion

Ne tenez pas compte des autres surcharges, regardez simplement l'espace occupé par Bucket : En PHP 5, compte tenu de l'alignement mémoire, l'espace occupé par unBucket fait 72 octets ; en PHP 7, un zend_valueoccupe 8 octets, unzvaloccupe 16 octets et unBucketoccupe 32 octets. En comparaison, la consommation d'espace mémoire deBucketdans PHP 7 est plus de moitié inférieure à celle de 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以双向链表的方式连接。

Implémentation du tableau : PHP5 VS PHP7

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

Implémentation du tableau : PHP5 VS PHP7

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

Copier après la connexion

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

⒉ 添加/修改元素

PHP 5

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

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

Copier après la connexion

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 中的实现方式直观。

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

Copier après la connexion

这里需要先说明一下nNumUsed和nNumOfElements

La consommation spécifique de mémoire des tableaux PHP 5 a été expliquée dans des articles précédents, je n'entrerai donc pas dans les détails ici

Implémentation du tableau : PHP5 VS PHP7

Parlons maintenant du stockage du Bucket: en PHP 5, arBucketest un tableau en langage C d'une longueur de nTableSize. Il stocke un pointeur vers Bucketet hash.se produit. Le Bucketen collision est connecté dans une liste doublement chaînée.

Dans PHP 7, Bucketest stocké dans l'ordre dans lequel les éléments du tableau sont écrits. Sa valeur d'index est idx, qui est stockée sur le côté gauche de *arData.dans la zone de mappage. L'index de idxdans la zone de mappage est nIndex, et la valeur nIndexest un nombre négatif, déterminé par le

du tableau keyLa valeur de hachageest combinée en OU avec
       nTableMask.
       
       
        
         // 删除 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; }
         
          Copier après la connexion
         
        
        
         Copier après la connexion
        
       Il convient de souligner ici que la raison pour laquelle
       nTableMaskest défini sur deux fois le
       nTableSizeest de réduire le
       hashlors du calcul de
       nIndex<. /code> code> Probabilité de collision. ⒉ Ajouter/modifier des éléments PHP 5
 Parlons d'abord de l'ajout et de la modification d'éléments de tableau en PHP 5. Depuis les tableaux en PHP 5, l'ordre d'insertion des éléments et les collisions de hachage sont maintenus via une liste doublement chaînée, donc même si c'est un peu compliqué à mettre en œuvre, c'est relativement facile à comprendre. #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); }
Copier après la connexion
Copier après la connexion
  Lors de l'ajout ou de la modification d'éléments à un tableau dans PHP 5, la valeur de hachage correspondante sera d'abord calculée en fonction de la clédonnée, puis la valeur de
       arBucketssera être obtenu en conséquence. Index
       nIndex, et enfin obtenir le premier
       Bucketde la liste chaînée (le
       hashentre en collision avec la tête de la liste chaînée), c'est-à-dire
       p.   Si vous mettez à jour un élément existant dans le tableau, alors la liste de collisions
       hashsera parcourue à partir de
       pjusqu'à ce que vous trouviez
       arkeyavec la
       clédonnée identique à
       Bucket, puis mettez à jour
       pData.   Si vous ajoutez un élément au tableau, il déterminera d'abord si la
       clédonnée est de type
       chaîne interne. Si tel est le cas, il suffit qu'elle soit
       
        Bucket< /code> demande de la mémoire, puis pointez
        p->arKeyvers l'adresse de la
        clédonnée, sinon ce sera un nouveau
        BucketLors de la demande de mémoire, vous devez également demander de la mémoire pour la
        clédonnée, puis pointer
        p->arKeyvers l'adresse de la mémoire appliquée pour
        clé. Ensuite, le bucket nouvellement appliqué sera initialisé et les deux dernières choses à faire sont de maintenir la liste chaînée de collision
        hashet la liste chaînée de séquence d'écriture d'éléments de tableau. Lors de la maintenance de la liste chaînée de collision de hachage, le bucket nouvellement ajouté est placé en tête de la liste chaînée ; lors de la maintenance de la liste chaînée de l'ordre d'écriture des éléments du tableau, le
        Bucketnouvellement ajouté est placé à la fin de la liste chaînée, et en même temps Le
        pListTailde
        hashtablepointe vers le
        Bucketnouvellement ajouté.
        
         Concernant la chaîne interne en PHP, elle a déjà été expliquée lors de l'explication de l'optimisation de la logique de traitement des chaînes en PHP 7, je n'entrerai donc pas dans les détails ici
        
        
         PHP 7
         PHP 7 a apporté des changements majeurs à la structure des données de la
        hashtable, et en même temps a abandonné l'utilisation de listes doublement chaînées pour maintenir le
        hash< /code> collisions et éléments du tableau. L'ordre d'écriture a été amélioré dans la gestion de la mémoire et les performances, mais il n'est pas aussi intuitif à comprendre que l'implémentation dans 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; }
Copier après la connexion
Copier après la connexion
  Ici, nous devons expliquer la différence entre nNumUsedet
        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 碰撞链表和数组元素写入顺序的链表。
        
         
          // 删除 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; }
          
           Copier après la connexion
          
         
         
          Copier après la connexion
         
        
          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); }
          
           Copier après la connexion
          
         
         
          Copier après la connexion
         
        
          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; }
          
           Copier après la connexion
          
         
         
          Copier après la connexion
         
        
        &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); \ }
         
          Copier après la connexion
         
        
          在新增元素时，如果当前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; }
         
          Copier après la connexion
         
        
          首先，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; }
         
          Copier après la connexion
         
        
          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); }
         
          Copier après la connexion
         
        
        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)); }
         
          Copier après la connexion
         
        
          另外，packed hashtable在扩容时，只需要将nTableSize翻倍，同时由于索引是升序排列的，所以Bucket的顺序不需要做任何调整，只需要重新分配内存空间即可。
        
         需要强调的是，packed hashtable只适用于索引为升序排列的索引数组（索引不一定要连续，中间可以有间隔）。如果索引数组的索引顺序被破坏，或索引中加入了字符串索引，那么此时packed hashtable会被转换为普通的hashtable。
        
        推荐学习：《PHP视频教程》
        Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!