In-depth understanding of PHP arrays (traversal order)

People often ask me, if a PHP array is accessed using foreach, is the order of traversal fixed? In what order?
For example:

. The code is as follows:

$ arr['laruence'] = 'huixinchen';
$arr['yahoo'] = 2007;
$arr['baidu'] = 2008;
foreach ($arr as $key => $val) {
/ /What is the result?
}

Another example:

. The code is as follows:

$arr[2] = 'huixinchen';
$arr[1] = 2007;
$ arr[0] = 2008;
foreach ($arr as $key => $val) {
//What is the result now?
}

To fully understand this issue, I think we should first ask everyone Understand the internal implementation structure of PHP arrays...

PHP arrays
In PHP, arrays are implemented using a HASH structure (HashTable). PHP uses some mechanisms to make it possible in O(1) time complexity It realizes the addition and deletion of arrays at a high speed, and supports linear traversal and random access at the same time.

We have also discussed PHP’s HASH algorithm in previous articles. Based on this, we will make further extensions.

Before getting to know HashTable, let us first look at it Looking at the structure definition of HashTable, I added comments for everyone to understand:

. The code is as follows:

typedef struct _hashtable {
uint nTableSize; /* Hash table size, range of Hash values*/
uint nTableMask; /* Equal to nTableSize -1, used for quick positioning*/
uint nNumOfElements; /* The number of actual elements in the HashTable*/
ulong nNextFreeElement; /* The numeric index of the next free available position*/
Bucket *pInternalPointer; /* Internal The position pointer will be reset and current. These traversal functions use */
Bucket *pListHead; /* Head element, used for linear traversal*/
Bucket *pListTail; /* Tail element, used for linear traversal*/
Bucket ** arBuckets; /* Actual storage container */
dtor_func_t pDestructor; /* Element destructor (pointer) */
zend_bool persistent;
unsigned char nApplyCount; /* Loop traversal protection */
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

Regarding the meaning of nApplyCount, we can understand it through an example:

. The code is as follows:

$arr = array(1, 2,3,4,5,);
$arr[] = &$arr;

var_export($arr); //Fatal error: Nesting level too deep - recursive dependency?

This field is for prevention and control Established to prevent infinite loops caused by circular references.

Looking at the above structure, we can see that for HashTable, the key element is arBuckets, which is the actual storage container. Let us take a look at its structure definition:

. The code is as follows:

typedef struct bucket {
ulong h; /* Numeric index/hash value*/
uint nKeyLength; /* Length of character index*/
void *pData; /* Data*/
void *pDataPtr ; /* Data pointer*/
struct bucket *pListNext; /* Next element, used for linear traversal*/
struct bucket *pListLast; /* Previous element, used for linear traversal*/
struct bucket *pNext; / * The next element in the same zipper */
struct bucket *pLast; /* The previous element in the same zipper */
char arKey[1]; /* Tips to save memory and facilitate initialization*/
} Bucket;

We noticed that the last element, this is a flexible array technique, which can save memory and facilitate initialization. Friends who are interested can google flexible array.
h is the Hash value of the element, for numerical indexing Element, h is the direct index value (numeric index represented by nKeyLength=0). For string index, the index value is stored in arKey, and the length of the index is stored in nKeyLength.
In the Bucket, the actual data It is stored in the memory block pointed to by the pData pointer. Usually this memory block is allocated separately by the system. But there is an exception, that is, when the data saved by the Bucket is a pointer, the HashTable will not request the system to allocate space to save the pointer, but directly save the pointer to pDataPtr, and then point pData to the member of this structure. the address of. This improves efficiency and reduces memory fragmentation. From this we can see the subtleties of PHP HashTable design. If the data in the Bucket is not a pointer, pDataPtr is NULL (this paragraph comes from Altair's "Zend HashTable Detailed Explanation")
The pListhHead of the HashTable points to the first element in the linear list form. In the above picture, it is element 1, and pListTail points to The last element is 0, and for each element pListNext is the next element of the linear structure drawn by the red line, and pListLast is the previous element.

pInternalPointer points to the position of the current internal pointer, when sequentially traversing the array , this pointer indicates the current element.

When linear (sequential) traversal is performed, it will start from pListHead, follow pListNext/pListLast in Bucket, and move pInternalPointer to achieve linear traversal of all elements.

For example, for foreach, if we look at the opcode sequence it generates, we can find that before foreach, there will first be a FE_RESET to reset the internal pointer of the array, which is pInternalPointer (for foreach, you can see In-depth Understanding of PHP Principles: foreach ), and then increment pInternalPointer each time FE_FETCH is used to achieve sequential traversal.

Similarly, when we use the each/next series of functions to traverse, we also achieve sequential traversal by moving the internal pointer of the array. Here is A question, for example:

. The code is as follows:

$arr = array(1,2,3,4,5);
foreach ($arr as $v) {
//Okay Get
}

while (list($key, $v) = each($arr)) {
//Cannot get
}
?>

Understanding the knowledge I just introduced, then this question It is very clear, because foreach will automatically reset, but the while block will not reset, so after foreach ends, pInternalPointer points to the end of the array, and of course the while statement block cannot be accessed. The solution is to reset before each. The internal pointer of the array.

During random access, the head pointer position in the hash array will be determined by the hash value, and then the characteristic element will be found through pNext/pLast.

When adding an element, the element will be inserted in The head of the same Hash element chain and the tail of the linear list. In other words, the elements are traversed according to the order of insertion during linear traversal. This special design makes it so that when using numerical indexes in PHP, the elements The order is determined by the order of addition, not the index order.

In other words, the order of traversing the array in PHP is related to the order of adding elements. So, now we clearly know that the beginning of the article The output of the problem is:

. The code is as follows:

huixinchen
2007
2008

So, if you want to iterate according to the index size in a numerically indexed array, then you should use for, not foreach

. The code is as follows:

for($i=0,$l=count($arr); $i<$l; $i++) {
//At this time, it cannot be considered as sequential traversal (linear traversal )
}

The above is an in-depth understanding of PHP arrays (traversal order). For more related articles, please pay attention to the PHP Chinese website (www.php.cn)!