PHP Internals — Array Traversal Order中文EN

People often ask me: if you traverse a PHP array with foreach, is the traversal order fixed? And what order is it, exactly?
For example:

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

And another example:

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

To understand this question completely, I think we first have to understand how PHP arrays are structured internally.........

PHP arrays

In PHP, an array is implemented with a hash structure (HashTable). PHP uses a set of mechanisms so that insertions and deletions can be done in O(1) time, while still supporting both linear traversal and random access.
I discussed some of this before in PHP's hash algorithm; here we'll take it a step further.
Before we get into HashTable, let's first look at its structure definition. I've added comments to make it easier to follow:

typedef struct _hashtable {
uint nTableSize;        /* size of the hash table, the range of hash values */
uint nTableMask;        /* equals nTableSize -1, used for fast positioning */
uint nNumOfElements;    /* number of elements actually in the HashTable */
ulong nNextFreeElement; /* next free numeric index available */
Bucket *pInternalPointer;   /* internal position pointer, used by reset, current and other traversal functions */
Bucket *pListHead;      /* head element, used for linear traversal */
Bucket *pListTail;      /* tail element, used for linear traversal */
Bucket **arBuckets;     /* the actual storage container */
dtor_func_t pDestructor;/* destructor (pointer) for elements */
zend_bool persistent;
unsigned char nApplyCount; /* recursion protection for traversal */
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

As for what nApplyCount means, an example will make it clear:

<?php
    $arr = array(1,2,3,4,5,);
    $arr[] = &$arr;
    var_export($arr); //Fatal error: Nesting level too deep - recursive dependency?

This field exists to prevent the infinite loop that a circular reference would otherwise cause.
Looking at the structure above, you can see that for a HashTable the key member is arBuckets, the actual storage container. Let's look at its structure definition:

typedef struct bucket {
ulong h;                        /* numeric index/hash value */
uint nKeyLength;                /* length of a string 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;                   /* next element in the same collision chain */
struct bucket *pLast;                   /* previous element in the same collision chain */
char arKey[1]; /* saves memory, convenient for initialization */
} Bucket;

Notice the last member. This is the flexible array trick, a way to save memory and simplify initialization. If you're curious, google "flexible array".
h is the element's hash value. For numerically indexed elements, h is the index itself (nKeyLength=0 marks it as a numeric index). For string indexes, the index itself is stored in arKey and its length is stored in nKeyLength.
Inside a Bucket, the actual data is kept in the memory block that pData points to, and normally that block is allocated separately by the system. There is one exception: when the data a Bucket holds is itself a pointer, HashTable will not ask the system for extra space to store the pointer. Instead it stores the pointer directly in pDataPtr and then points pData at the address of that member. This improves efficiency and reduces memory fragmentation. From this you can see the elegance of PHP's HashTable design. If the data in the Bucket is not a pointer, pDataPtr is NULL. (This paragraph comes from Altair's "Zend HashTable in Detail")
Together with the HashTable structure above, here is the overall layout of a HashTable:

HashTable's pListHead points to the first element in the linear list, which is element 1 in the figure above, and pListTail points to the last element, 0. For each element, pListNext is the next element in the linear structure drawn with the red lines, and pListLast is the previous one.
pInternalPointer points to the current position of the internal pointer. When an array is traversed in order, this pointer identifies the current element.
During a linear (sequential) traversal, PHP starts from pListHead and follows the pListNext/pListLast links inside the Bucket, moving pInternalPointer along, so that every element is visited in linear order.
For foreach, for instance, if we look at the opcode sequence it generates, we find that before the loop there is a FE_RESET that resets the array's internal pointer, that is, pInternalPointer (see PHP Internals — foreach for more on foreach), and then each FE_FETCH advances pInternalPointer, which is what produces the sequential traversal.
Similarly, when we traverse with the each/next family of functions, sequential traversal is again achieved by moving the array's internal pointer. And here there is a problem, for example:

<?php
$arr = array(1,2,3,4,5);
foreach ($arr as $v) {
//can be accessed
}
while (list($key, $v) = each($arr)) {
//cannot be accessed
}
?>

With what I've just explained, this problem becomes obvious: foreach resets automatically, while the while block does not. So once the foreach has finished, pInternalPointer points to the very end of the array, and the while block of course gets nothing. The solution is to reset the array's internal pointer before calling each.
For random access, the hash value determines the head pointer position in the hash array, and pNext/pLast are then used to find the particular element.
When an element is added, it is inserted at the head of the chain of elements with the same hash and at the tail of the linear list. In other words, elements are traversed in linear order according to the order in which they were inserted. This particular design means that in PHP, when numeric indexes are used, the order of elements is determined by the order in which they were added, not by index order.
So the order in which PHP traverses an array depends on the order in which elements were added. Which means we now know clearly what the examples at the beginning of this post output:

huixinchen
2007
2008

So if you want to traverse a numerically indexed array in index order, you should use for, not foreach:

for($i=0,$l=count($arr); $i<$l; $i++) {
 //at this point, this cannot be considered a sequential (linear) traversal
}