php array lookup time

Question

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.

How does array_keys do the search for value? read the comments in the accepted answer. — ThinkingMonkey
– ThinkingMonkey, Commented Jan 4, 2012 at 17:23
Maybe you will be interested also in this article nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html — Peter Krejci
– Peter Krejci, Commented Jan 4, 2012 at 17:25

Community · Accepted Answer · 2017-05-23 12:12:09Z

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?

edited May 23, 2017 at 12:12

CommunityBot

11 silver badge

answered Jan 4, 2012 at 17:17

Tobias

9,4203 gold badges27 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

lollercoaster Over a year ago

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

Collectives™ on Stack Overflow

php array lookup time

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related