How is the PHP array implemented on the C level?

Solution 1:

After reading over zend/zend_hash.h and ext/standard/array.c I think I have found the answer (Thankyou Chris and gumbo for the suggestions).

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. Also each value stored in the hash is linked to the value stored before it and the value stored after (linked list). It also has a temporary pointer which is used to hold the current item so the hash can be iterated.

The catch for the array_rand function is that in order to assure that key is truly random, the array_rand function must iterate over the array rand(0, count($array)) times (O(n)). This is because there is no way to move to an offset in the hash table in O(c) time because there is no guarantee that there isn't missing keys in the range.

This discovery has somewhat troubled me, because it means there is NO datatype in PHP that has normal C array characteristics. Now most of the time this is ok, because hash lookups are very faster, but it's faults show through in cases like array_rand.

Another thing that also troubled me was the difference between the implementation of array_key_exists and in_array. array_key_exists uses the hash lookup (most of the time O(c)) to see if a key is in the array, while in_array has to linearly search the hash (O(n)).

Consider the two examples below:

in_array version

$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
   //we found a value
}

array_key_exists version

$array = array_fill_keys( range(0, 100000), NULL );
if( array_key_exists( $random_key, $array ) ) {
   //we found a value, err key
}

While the in_array version looks much cleaner and simpler to understand, it's actually very slow on large arrays (O(n)), where array_key_exists (despite is annoyingly long name) is very fast (O(c) or close).

In conclusion: I wish there was a transparent flag in the zend HashTable data-structure that would be set in cases where the array was created using array_push or array[] = $value that would allow for scaling like a C array instead of a linked list.

Solution 2:

PHP associative arrays are in fact implementation of HashTables.

Internally, it is possible to make numeric arrays or associative arrays. If you combine them, it is associative array.

In numeric arrays, it is very similar to C. You have array of pointers to ZVAL structs.

Because pointers have fixed-length (let's call it n), the offset (x) calculation is easy: x * n.

In PHP types are ZVAL structs (because that way it implements dynamic types), but it also helps in associative array, because you can assume fixed-length. So even if direct access to array is slower, it is still considered O(1).

So what happens in string keys? PHP uses hash function to convert them to intergers.

Searching in numeric and associative array has similar efficiency, because internally they are all numeric.

Only direct-access to array keys is slower, because of the additional level (hash function).

Solution 3:

Since PHP arrays are ordered maps (even when using contiguous integer indices) array_rand() likely has to cons up a list of keys to select an element from. I'm guessing that it would be prohibitively space and time ineffective to cache the (frequently invalidated) key list so every call is going to incur at least an O(n) traversal and construction cost.

Because your rand(... length ...) implementation takes advantage of the special knowledge you have that the keys are contiguous integers, you'll get O(log n) lookup costs. This seems consistent with Chacha102's data.