Can someone explain how PHP implements associative arrays? What underlying data structure does PHP use? Does PHP hash the key and store it in some kind of hash map? I am curious because I was wondering what the performance of associative arrays where when inserting and searching for keys.
+3
A:
Well, for what it is worth, all PHP arrays are Associative arrays.
EBGreen
2008-10-29 16:28:22
+3
A:
I'll leave this link for someone else to grind through, but you can view the actual C source for PHP at
kthejoker
2008-10-29 16:48:39
+1
A:
It's all hash tables, according to sources in various web forums: http://www.usenet-forums.com/php-language/15348-zend-engine-array-implementation.html
If you want to be sure, read the source, then compile it, but make sure you can trust your compiler (Warning: PDF, and unrelated, but very cool).
jakber
2008-10-29 16:52:05
+4
A:
@EBGreen is correct.
Which gives you some interesting performance problems, especially when treating an array as a list and using the [] (array add) operator. PHP doesn't seem to cache the largest numeric key and add one to it, instead it seems to traverse all of the keys to find what the next numeric key should be. I've rewritten scripts in python because of PHP's dismal array-as-a-list performance.
Associative arrays have the standard dict/hash performance overhead.
jcoby
2008-10-29 17:14:36
Are you sure about this? I've just ran benchmarks on a test array of 1000 entries (copying to a new array, one by one), and if you don't specify the key for the new array, it's consistently 7% faster (on PHP 5.2.6)
JamShady
2008-10-29 21:08:14
It's possible they've changed it recently. I was using 5.1 when I was doing the work. PHP's array was AWFUL when you're talking about 10k entries or more.
jcoby
2008-10-29 21:46:37
+1
A:
It's a hash table. The type declaration and hashing function are here: http://cvs.php.net/viewvc.cgi/ZendEngine2/zend_hash.h?view=markup
There is a light weight array and a linked list within the spl (standard php lib)
chuck
2010-04-22 18:54:11