How is the PHP array implemented on the C level?
arrays, php
Solution
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).
Problem
The PHP `array` is one of PHP's core features. It is sparse, allows multi-typed keys in the same array, and supports set, dictionary, array, stack/queue and iterative functionality. But after working with PHP for a while now, I've found that quite a few of the `array_*` functions are much slower than you'd think at first glance. Like in the case of `array_rand` on a very large array (10000+). `array_rand` is so slow in fact, that in cases where your using the php array as an indexed array, a function like `rand( 0, array_length( $array ) - 1 )` runs MUCH faster than `array_rand`. Now onto my question. How is the PHP array implemented on the C level? This would be very helpful for predicting the Big O of a function that heavily uses the different functionality of the PHP array datatype.