2

I just thought I would comb through this to find the answer: http://svn.php.net/viewvc/php/php-src/

But I couldn't find it. In C++ <map> is implemented as a balanced binary search tree with const key values. this is nice, you get O(log n) search, insert, delete, etc runtimes. O(n) enumeration time.

What I'm wondering is the underlying data structure of PHP arrays. There are a few SO posts on PHP arrays that say "well they do pretty much the same thing, so don't worry about it!". not what I'm after. Is it O(1) (hash table) or O(log n) (balanced binary tree) lookup? (for example)

If anyone can help me out or point me to the right PHP C source file, that would be awesome (though a little explanation would be good - I'm really bad at C). Or if you just have cool insights about PHP arrays that's good as well - I'm trying to understand the entire underlying data structure.

lollercoaster
  • 15,969
  • 35
  • 115
  • 173
  • 1
    [How does array_keys do the search for value?](http://stackoverflow.com/q/8659224/858515) `read the comments in the accepted answer.` – ThinkingMonkey Jan 04 '12 at 17:23
  • 1
    Maybe you will be interested also in this article http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html – Peter Krejci Jan 04 '12 at 17:25

1 Answers1

2

An array in PHP is actually an ordered map. A map is a type that associates values to keys. This type is optimized for several different uses; it can be treated as an array, list (vector), hash table (an implementation of a map), dictionary, collection, stack, queue, and probably more. As array values can be other arrays, trees and multidimensional arrays are also possible.

The implementation is in fact some sort of a HashTable.

-> http://php.net/manual/en/language.types.array.php
-> How is the PHP array implemented on the C level?

Community
  • 1
  • 1
Tobias
  • 9,170
  • 3
  • 24
  • 30
  • that's really not the answer I'm looking for. so php decides how it is "treated" at runtime (or bytecode compilation time)? because an ordered map is a balanced binary tree - which by definition can't have an `O(1)` lookup time like a hash table – lollercoaster Jan 04 '12 at 17:19