Looking for more information on how to do PHP the right way? Check out PHP: The Right Way

Nikita Popov's Blog:
Supercolliding a PHP array
Dec 29, 2011 @ 12:15:30

In a new post to his blog Nikita Popov talks about a little trick with inserting values into arrays that can make it take a lot longer than it should (because of how PHP stores its array values in hashtables).

PHP internally uses hashtables to store arrays. The above creates a hashtable with 100% collisions (i.e. all keys will have the same hash). [...] Because every hash function has collisions this C array doesn't actually store the value we want, but a linked list of possible values. [...] Normally there will be only a small number of collisions, so in most cases the linked list will only have one value. But the [included script] creates a hash where all elements collide.

He explains why it works, noting that it's relatively simple to do in PHP because of how it applies a table mask. The slowness comes in when PHP is forced to go through the entire list when it tries to insert. Because of this issue, there's the potential for a Denial of Service attack that could potentially take a server down. There's a fix already in place for the problem, though, so keep an eye out for the next release (that will include a max_input_vars setting to prevent it).

tagged: collision array hashtable mask denialofservice overload