Shulou(Shulou.com)06/03 Report--

Editor to share with you what is the difference between the array implementation of PHP5 and PHP7, I believe most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to know it!

From PHP 5 to PHP 7, PHP has greatly improved the memory footprint and performance of arrays by modifying the data structure and implementation of hashtable.

⒈ data structure

/ / the data structure of hashtable in PHP 5 defines typedef struct bucket {ulong h; / * for indexed arrays, store the original value of key For associative arrays, store the value after the hash of key * / uint nKeyLength; / * the length of the storage key when associating the array, and the indexed array with a value of zero / void * pData; / * points to the address of the array value * / void * pDataPtr / * record bucket's C language array * / dtor_func_t pDestructor; / * the function called internally when deleting array elements * / zend_bool persistent; / * identifies whether the ht is permanently valid * / unsigned char nApplyCount; / * the maximum recursive depth allowed by ht * / zend_bool bApplyProtection; / * whether recursive protection is enabled * / # if ZEND_DEBUG int inconsistent;#endif} HashTable / / the data structure of hashtable in PHP 7 / / there is a slight difference in the definition of hashtable data structure between the sub-version of PHP 7 and the phase version. Here the definition struct _ zend_string {zend_refcounted_h gc; zend_ulong h; / * the hash value of the string key * / size_t len is used in PHP 7.4.0. / * the length of the string key * / char val [1]; / * stores the value of the string, using struct hack*/}; typedef struct _ Bucket {zval val; / * embedded zval structure to store the value value of the array * / 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 / * the function is the same as that of nTableMask in hashtable in PHP 5, but the implementation logic changes slightly * / Bucket * arData; / * Storage bucket related information * / uint32_t nNumUsed; / * the number of bucket already used in ht, plus deleted key*/ uint32_t nNumOfElements; uint32_t nTableSize; uint32_t nInternalPointer on the basis of nNumOfElements Zend_long nNextFreeElement; dtor_func_t pDestructor;}

   does not take into account other overhead, just in terms of the space consumed by Bucket: in PHP 5, considering memory alignment, a Bucket takes up 72 bytes; in PHP 7, a zend_value takes 8 bytes, an zval 16 bytes, and a Bucket 32 bytes. By contrast, the memory space consumption of Bucket in PHP 7 is more than half that of PHP 5.

The specific memory consumption of PHP 5 array has been explained in previous articles, so I won't repeat it here.

   now talk about the storage of Bucket: in PHP 5, arBucket is a C-language array of length nTableSize that stores pointers to Bucket, and Bucket that collides with hash is connected in a two-way linked list.

   in PHP 7, Bucket is stored in the order in which array elements are written, with an index value of idx, which is stored in the mapping area to the left of * arData. The index of idx in the mapping area is a negative nIndex,nIndex value, which is obtained by the or operation of the hash value of the array key with nTableMask.

   follows the example in the figure, where the value of nNumUsed should be 5, but the value of nNumOfElements should be 3. In PHP 7, array elements are stored in the order in which they are written, and nNumUsed can be used to serve as an index of where array elements are stored.

   is also p = arData + idx. As mentioned earlier, arData is of type Bucket, where + idx means that the pointer offsets the position of idx Bucket to the right from the position of arData. The same is true for macro calls to HT_HASH_EX.

At the end of    is Z_NEXT (p-> val). The Bucket structure in PHP 7 has an embedded zval,zval consortium U2. There is an next entry used to record hash collision information. NIndex is used to identify the location of idx in the mapping table. When adding elements to hashtable, if the location of nIndex calculated based on a given key already has a value (that is, a hash collision has occurred), then the original value of the location pointed to by nIndex needs to be recorded in the val.u2.next under the Bucket corresponding to the new element. The purpose of macro call HT_IDX_TO_HASH is to calculate the offset of Bucket in bytes based on idx.

⒊ delete element

PHP 5

   in PHP 5, the main work in the process of deleting array elements is to maintain the hash collision linked list and the linked list in which array elements are written.

/ delete Bucket code (streamlined some code snippets) 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) } / / element deletion 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;}

When deleting elements in    PHP 5, the array still calculates the hash based on the given key, then finds the nIndex of the arBucket, and finally finds the linked list of the hash collision where the Bucket is to be deleted, and finds the Bucket that needs to be deleted by traversing the linked list.

In the process of actually deleting Bucket, what    mainly does is to maintain two linked lists: the hash collision linked list and the array element write sequential linked list. Then there is the release of memory.

PHP 7

   due to the change in the way PHP 7 records hash collision information, the logic for handling hash collision lists when deleting elements is also different. In addition, space reclamation may be encountered when deleting elements.

# 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) {/ / remove the specified Bucket if (! (HT_FLAGS (ht) & HASH_FLAG_PACKED)) {if (prev) {Z_NEXT (prev- > val) = Z_NEXT (p-> val) from the hash collision list } 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) {/ / if the internal pointer of the current hashtable points to the Bucket to be deleted or the current hashtable has an ergodic / / operation, you need to avoid the Bucket uint32_t new_idx; new_idx = idx; while (1) {new_idx++ that is currently being deleted If (new_idx > = ht- > nNumUsed) {break;} else if (Z_TYPE (ht- > Arta [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) {/ / if the deleted Bucket is at the end of the array, the deleted Bucket space do {ht- > nNumUsed-- adjacent to the Bucket is also reclaimed. } while (ht- > nNumUsed > 0 & & (UNEXPECTED (ht- > arta [ht-> nNumUsed-1] .val) = = IS_UNDEF)); ht- > nInternalPointer = MIN (ht- > nInternalPointer, ht- > nNumUsed);} if (p-> key) {/ / delete string type index zend_string_release (p-> key);} / delete 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)) {/ / if the deleted Bucket has a hash collision, you need to find out its position in the hash collision list 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);}

The ultimate goal of the deletion of array elements in    PHP 7 is to delete the specified Bucket. When deleting Bucket, you also need to deal with the maintenance of hash collision linked list. Since hash collisions in PHP 7 only maintain an one-way linked list (maintained by Bucket.val.u2.next), you also need to find the previous prev in the hash collision list when deleting the Bucket. Finally, when deleting a Bucket, if the internal pointer (nInternalPointer) of the current hashtable happens to point to the Bucket to be deleted or there is a traversal operation, you need to change the direction of the internal pointer and skip the Bucket to be deleted during traversal. In addition, it should be pointed out that the corresponding memory space is not reclaimed every time the Bucket is deleted. Usually, deleting Bucket only marks the type of val in it as IS_UNDEF, and reclaims its memory space only when the Bucket to be deleted is the last and the adjacent Bucket is IS_UNDEF.

⒋ array traversal

PHP 5

   because PHP 5 has a bi-directional linked list specifically used to record the write order of array elements, the traversal logic of the array is relatively simple.

/ / forward traversal of array 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;} / / reverse traversal of array 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;}

There are three fields in the data structure of hashtable in emsp;   PHP 5: pInternalPointer is used to record the address of the current Bucket pointed to by the pointer during array traversal; pListHead is used to record the header of the bidirectional linked list that holds the write order of array elements; and pListTail is used to record the footer of the bidirectional linked list that holds the write order of array elements. The forward traversal of the array starts at the location of the pListHead and is achieved by constantly updating the pInternalPointer, while the reverse traversal starts with the pListTail and is achieved by constantly updating the pInternalPointer.

PHP 7

   because the elements of the array in PHP 7 are stored in the order in which they are written, the logic of traversal is relatively simple, except that items marked as IS_UNDEF need to be skipped during traversal.

⒌ hash collision

PHP 5

   mentioned earlier when talking about the addition / modification of array elements. Every time a new element is added to the array, the hash collision, namely CONNECT_TO_BUCKET_DLLIST, is checked and handled. The code is as follows

CONNECT_TO_BUCKET_DLLIST (p, ht- > arBuckets [n Index]); # define CONNECT_TO_BUCKET_DLLIST (element, list_head)\ (element)-> pNext = (list_head);\ (element)-> pLast = NULL \ if ((element)-> pNext) {\ (element)-> pNext- > pLast = (element);\}

When    adds elements, if there are no other elements in the current arBuckets location, you only need to write to the new Bucket directly, otherwise the new Bucket will be written to the header position of the hash collision two-way linked list.

PHP 7

As    mentioned earlier, hashtable in PHP 7 maintains an one-way linked list of hash collisions through the val.u2.next entry in Bucket. So, when you add a new element to the hashtable, you finally need to write the value of the nIndex location into the val.u2.next of the new Bucket. When deleting a Bucket, you need to find out the previous item in the hash collision list where the Bucket to be deleted is located in order to maintain the subsequent hash collision list.

⒍ capacity expansion

PHP 5

   has a line of code ZEND_HASH_IF_FULL_DO_RESIZE (ht) at the end of the API added / modified by array elements to determine whether the current hashtable needs to be expanded, and expand it if necessary.

/ / determine whether the current hashtable needs to be expanded # define ZEND_HASH_IF_FULL_DO_RESIZE (ht)\ if ((ht)-> nNumOfElements > (ht)-> nTableSize) {\ zend_hash_do_resize (ht);\} / / hashtable expansion (streamlined partial code) ZEND_API int zend_hash_do_resize (HashTable * ht) {Bucket * * t If ((ht- > nTableSize 0) {/ * Let's double the table size * / t = (Bucket * *) perealloc (ht- > arBuckets, (ht- > nTableSize persistent); ht- > arBuckets = t; ht- > nTableSize = (ht- > nTableSize nTableMask = ht- > nTableSize-1; zend_hash_rehash (ht) }} / / rehash the elements in hashtable (simplified partial code) 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 [n Index]); ht- > arBuckets [nIndex] = p;} return SUCCESS;}

   first, the prerequisite for PHP 5 hashtable expansion: the number of elements in the array exceeds the value of hashtable's nTableSize. After that, the nTableSize of hashtable doubles, and then the memory space is reallocated for arBuckets and the value of nTableMask is updated. Finally, because the nTableMask changes, you need to recalculate the nIndex based on the index of the array elements, and then associate the previous Bucket to the new location in the newly allocated arBuckets.

PHP 7

   also has a code ZEND_HASH_IF_FULL_DO_RESIZE (ht) to determine whether it needs to be expanded in the API of adding / modifying hashtable in PHP 7. When the condition is met, the expansion operation will be performed.

# 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)) / / when the nNumUsed of hashtable is greater than or equal to nTableSize, perform the expansion operation # 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) / / capacity expansion (partial code reduction) 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)

< 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 (partial Code reduction) 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 not marked as IS_UNDEF item do {nIndex = p-> h | ht- > nTableMask; Z_NEXT (p-> val) = HT_HASH (ht, nIndex) HT_HASH (ht, nIndex) = HT_IDX_TO_HASH (I); pairing;} while (+ + I)

< ht->

NNumUsed);} else {/ / Bucket has the item marked IS_UNDEF uint32_t old_num_used = ht- > nNumUsed; do {if (UNEXPECTED (Z_TYPE (p-> val) = = IS_UNDEF)) {/ / Bucket the first item is marked IS_UNDEF uint32_t j = I; Bucket * Q = p If (EXPECTED (! HT_HAS_ITERATORS (ht) {/ / hashtable has no traversal operation while (+ + I)

< ht->

NNumUsed) {pairing; 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;} qroomrooms; jacks + } else {/ / hashtable there is a traversal operation uint32_t iter_pos = zend_hash_iterators_lower_pos (ht, 0); while (+ + I

< ht->

NNumUsed) {pairing; 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); pendant;} 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;}

Hashtable in    PHP 7 also doubles the nTableSize during capacity expansion, and then rehash. During the rehash operation, if there is no IS_UNDEF marked for deletion in the Bucket, the storage order of the Bucket will not change after the rehash operation, but the storage location of the idx index will change due to the change of the nTableMask, which will eventually lead to the change of the hash collision linked list. If there are items in the Bucket that are marked for deletion, these Bucket items are skipped during the rehash process, leaving only those items that have not been deleted. At the same time, because this will cause the index of the Bucket to change compared with the original, it is necessary to update the information of the internal pointer of hashtable and the information related to the traversal operation at the same time in the process of rehash.

Packed hashtable in ⒎ PHP 7

   in PHP 7, if an array is an indexed array and the indexes in the array are arranged in ascending order, then because the Bucket in hashtable is in write order, and the array index is in ascending order, the mapping table is no longer necessary. PHP 7 makes some packed hashtable optimizations for hashtable for this particular situation.

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

When    packed hashtable is initialized, the value of nTableMask defaults to-2 and is marked in the flags of hashtable. If there are no elements in the packed hashtable at this time, the nTableSize will be set to 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);}

   in addition, when packed hashtable expands its capacity, it only needs to double the nTableSize, and because the indexes are arranged in ascending order, the order of Bucket does not need to be adjusted, only memory space needs to be reallocated.

It is important to emphasize that packed hashtable applies only to indexed arrays whose indexes are arranged in ascending order (indexes do not have to be contiguous and can be spaced). If the index order of the index array is broken, or if a string index is added to the index, then the packed hashtable will be converted to a normal hashtable.

I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.