How does PHP keep track of order in an associative array?

Question

When pushing a new value onto an indexed array

$array[] = 'new value';

the PHP documentation explains how it gets added in the [MAX_INDEX+1] position.

When pushing a new value onto an associative array

$array['key'] = 'new value';

it works the same, but I don't see any explanation in the documentation to confirm how or why it does so. The order seems to be consistent in my implementation, but how do I know for sure that the order will remain the same? Does anyone know how PHP implements this on the back-end?

Answer 1

MAX_INDEX actually has nothing to do with ordering.
you can do

$array[5] = 'new value';
$array[1] = 'new value';
$array[105] = 'new value';
$array[2] = 'new value';

and this array will keep that order as well.

PHP array is an ordered map, so, it's a map that keeps the order.
array elements just keep the order since they were added that's all.

Answer 2

All PHP Arrays, numeric and associative, are implemented as a so-called "Ordered Hash-Table". This is a data science term which amounts to: "A reasonable fast key-value store that keeps track of the order in which keys and values were inserted". In other words, PHP arrays have a bit of memory bolted on for the purpose of remembering order. Every time you put something in it, PHP automatically puts the order in there as well.

Interestingly, this happens for numeric keys as well- so if you put the values 1,2,3,4,5 into a PHP array, PHP is still separately keeping track of the order. If this sounds wasteful, that's because it is! It does, however, save brain cycles, that can be used to solve other poeple's problems, real and imagined.

Answer 3

How are associative arrays implemented in PHP? might give you some insight.

It seems that PHP arrays are essentially hash tables, so the order of the array will stay the same until you reorder it (e.g. by sorting the array).

EDIT: It appears this is getting downvoted, allow me to explicitly include the sources I linked to in the comment below here...

• "PHP associative arrays are in fact an implementation of HashTables", from How is the PHP array implemented on the C level?

• Also from that source: "The PHP array is a chained hash table (lookup of O(c) and O(n) on key collisions) that allows for int and string keys. It uses 2 different hashing algorithms to fit the two types into the same hash key space."

• "Everything is a HashTable" from http://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html