Reputation:

How are associative arrays implemented in PHP?

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.

Upvotes: 26

Answers (5)

PressingOnAlways

Reputation: 12356

The highest voted answer link is broken and doesn't give that much explanation.

PHP is written in C and the underlying structure is just a C array. C arrays are just chunks of memory. The indexes in C arrays must be continuous, you can't have an index 0 and an index 1000 that comes after it. To make associative array keys work, before they are added to the C array, they are converted to proper C indices via a hash function.

For a full explanation, I found this link to be much more informative.

http://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html

Upvotes: 8

chuck

Reputation: 71

It's a hash table. The type declaration and hashing function are here:
http://svn.php.net/viewvc/php/php-src/trunk/Zend/zend_hash.h?view=markup

There is a light weight array and a linked list within the spl (standard php lib)

Upvotes: 7

jcoby

Reputation: 4260

@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.

Upvotes: 3