how are php arrays indexed?

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View
Hi everyone,

I'm wondering if anyone knows whether PHP does some indexing behind
the scenes to make array searches faster.

What I have is an array of around 100 000 elements, and I have a list
of 1000 given element which I need to see whether they contained in
the array. This means 1000 searches on an array of size 100 000. I'm
hoping that PHP indexes it's keys using a binary tree or
something.. :)



Re: how are php arrays indexed?

On 16.05.2007 13:01 Taras_96 wrote:
Quoted text here. Click to load it

php uses hash function to speed up access to array elements, namely  
Bernstein's function, also known as "times 33"

gosha bine

extended php parser ~
blok ~

Re: how are php arrays indexed?

Taras_96 wrote:

Quoted text here. Click to load it


PHP used hashing.  
I understand it is all very fast, but it was many years ago I learned the  
logic behind it, so I forgot all about the linked lists and stuff like  
that, and cannot be of help there.

But looking up 1000 values inside 100.000 can easily be done by using  
specialized array functions, like:

Look them up at

You can bet the alghoritm used behind the scenes is optimized C-code, and  
probably unbeatable by your own routines.

I would give them a shot first. If still too slow, ask again. :-)

Erwin Moller

Quoted text here. Click to load it

Re: how are php arrays indexed?

At Wed, 16 May 2007 04:01:37 -0700, Taras_96 let his monkeys type:

Quoted text here. Click to load it

Just gave your example a test run with two arrays full of random values
using array_intersect. On my localhost it takes about 2.45 seconds, so
you have an idea of the order of magnitude.

$myarray = array();
for ($i=0;$i<100000;$i++) {
$mytestarray = array();
for ($i=0;$i<1000;$i++) {

$start = microtime(true);
$stop = microtime(true);
echo $stop-$start; // avg 2.45 secs on P4-3200MHz, PHP sapi/Apache

The returned array still has the keys of the first array's matching
locations. Whether you get a large intersection or not doesn't seem to be
of great influence.

How much memory do you have available to your PHP scripts? If I make the
original array 150.000 elements 16Mb doesn't suffice anymore in above
example. If your data is more complex than my ints, this might become an


Re: how are php arrays indexed?

Quoted text here. Click to load it

As others have pointed out, arrays in PHP are hash tables. To search
quickly, you'd want to take advantage of that. For example, if you're
writing a spell-checker, you wouldn't want to store the word list like

array("a", "able", "above", ...)

but rather like this:

array("a" => 1, "able" => 1, "above" => 1);

then check for existence of a word by accessing the array using the
word as the key.

Site Timeline