In diesem Artikel vergleichen Sie die Array-Implementierungen von PHP5 und PHP7 und sehen die Unterschiede zwischen ihnen!
Von PHP 5 bis PHP 7 hat PHP die Speichernutzung und Leistung von Arrays durch Änderungen an der Hashtable-Datenstruktur und -Implementierung erheblich verbessert.
⒈ Datenstruktur
// 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; };
Berücksichtigen Sie keine anderen Overheads, sondern schauen Sie sich nur den von Bucket belegten Platz an: In PHP 5 wird unter Berücksichtigung der Speicherausrichtung der von einem Bucket</code belegte Platz berücksichtigt > ist 72 Bytes; in PHP 7 belegt ein <code>zend_value
8 Bytes, ein zval
16 Bytes und ein Bucket
32 Bytes. Im Vergleich dazu ist der Speicherplatzverbrauch von Bucket
in PHP 7 mehr als die Hälfte niedriger als in 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
进行或运算得到。
// 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);
这里需要指出,nTableMask
之所以设置为 nTableSize
的两倍,是这样在计算 nIndex
时可以减小 hash
碰撞的概率。
⒉ 添加/修改元素
先来谈谈 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; }
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 在 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; }
这里需要先说明一下 nNumUsed
和 nNumOfElements
Der spezifische Speicherverbrauch von PHP 5-Arrays wurde in früheren Artikeln erläutert, daher werde ich hier nicht auf Details eingehenLassen Sie uns nun über die Speicherung von
Bucket
sprechen : In PHP 5 ist arBucket
ein C-Spracharray mit einer Länge von nTableSize
. Es speichert einen Zeiger auf Bucket
und einen Hash
tritt auf. Die kollidierenden Buckets
werden in einer doppelt verknüpften Liste verbunden. 🎜🎜🎜 In PHP 7, Bucket
wird in der Reihenfolge gespeichert, in der die Array-Elemente geschrieben werden. Sein Indexwert ist idx
, der auf der linken Seite von *arData gespeichert wird
im Mapping-Bereich. Der Index von idx
im Zuordnungsbereich ist nIndex
, und der Wert von nIndex
ist eine negative Zahl, die durch den des Arrays bestimmt wird <code>key
Der Hash-Wert wird mit nTableMask
ODER-verknüpft. 🎜🎜🎜// 删除 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; }
nTableMask
auf das Doppelte von nTableSize
gesetzt wird, damit der Hash</ bei der Berechnung von <code>nIndex reduziert werden kann
code> Kollisionswahrscheinlichkeit. 🎜🎜🎜🎜⒉ Elemente hinzufügen/ändern 🎜🎜🎜#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); }
key
und dann dem entsprechenden Hash-Wert von arBuckets</code berechnet > wird entsprechend abgerufen. Indexieren Sie <code>nIndex
und erhalten Sie schließlich den ersten Bucket
in der verknüpften Liste (hash
kollidiert mit dem Kopf der verknüpften Liste ), also p
. 🎜🎜 Wenn Sie ein vorhandenes Element im Array aktualisieren, wird die hash
-Kollisionsliste beginnend mit p
durchlaufen, bis Sie arkey
mit finden Der angegebene key
ist der gleiche wie bei Bucket
, dann aktualisieren Sie pData
. 🎜🎜 Wenn Sie dem Array ein Element hinzufügen, wird zunächst ermittelt, ob der angegebene key
vom Typ interned string
ist. Wenn ja, muss es nur Bucket< /code> beantragt Speicher und zeigt dann p->arKey
auf die Adresse des angegebenen Schlüssels
, andernfalls handelt es sich um einen neuen Bucket
Wenn Sie Speicher beantragen, müssen Sie auch Speicher für den angegebenen Schlüssel
beantragen und dann p->arKey
auf die Adresse des angewendeten Speichers verweisen für key
. Anschließend wird der neu angewendete Bucket initialisiert, und die letzten beiden Dinge, die Sie tun müssen, sind die Pflege der verknüpften Liste mit Hash
-Kollisionen und der verknüpften Liste mit der Array-Element-Schreibsequenz. Wenn die verknüpfte Liste der Hash-Kollisionen verwaltet wird, wird der neu hinzugefügte Bucket an der Spitze der verknüpften Liste platziert. Wenn die verknüpfte Liste die Schreibreihenfolge der Array-Elemente verwaltet, wird der neu hinzugefügte Bucket
platziert das Ende der verknüpften Liste und gleichzeitig Der pListTail
von hashtable
zeigt auf den neu hinzugefügten Bucket
. 🎜🎜 Was den internierten String in PHP betrifft, wurde er bereits bei der Erläuterung der Optimierung der String-Verarbeitungslogik in PHP 7 erläutert, daher werde ich hier nicht auf Details eingehen🎜
- 🎜PHP 7🎜
🎜 PHP 7 hat wesentliche Änderungen an der Datenstruktur von hashtable
vorgenommen und gleichzeitig die Verwendung doppelt verknüpfter Listen zur Verwaltung von hash< aufgegeben /code>-Kollisionen und Array-Elemente Die Schreibreihenfolge wurde hinsichtlich Speicherverwaltung und Leistung verbessert, ist jedoch nicht so intuitiv zu verstehen wie die Implementierung in PHP 5. 🎜<div class="code" style="position:relative; padding:0px; margin:0px;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false;">// 数组的正向遍历
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;
}</pre><div class="contentsignin">Nach dem Login kopieren</div></div><div class="contentsignin">Nach dem Login kopieren</div></div>🎜 Der Unterschied zwischen <code>nNumUsed
und nNumOfElements
muss zuerst erklärt werden: 🎜🎜🎜🎜 按图中示例,此时 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;
}
Nach dem Login kopierenNach dem Login kopieren 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);
}
Nach dem Login kopierenNach dem Login kopieren 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;
}
Nach dem Login kopierenNach dem Login kopieren&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); \
}
Nach dem Login kopieren 在新增元素时,如果当前 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;
}
Nach dem Login kopieren 首先,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;
}
Nach dem Login kopieren 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);
}
Nach dem Login kopieren 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));
}
Nach dem Login kopieren 另外,packed hashtable
在扩容时,只需要将 nTableSize
翻倍,同时由于索引是升序排列的,所以 Bucket
的顺序不需要做任何调整,只需要重新分配内存空间即可。
需要强调的是,packed hashtable
只适用于索引为升序排列的索引数组(索引不一定要连续,中间可以有间隔)。如果索引数组的索引顺序被破坏,或索引中加入了字符串索引,那么此时 packed hashtable
会被转换为普通的 hashtable
。
推荐学习:《PHP视频教程》
Das obige ist der detaillierte Inhalt vonArray-Implementierung: PHP5 VS PHP7. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!