Obsolete:PHP hashtable collisions

I would have gone up to 65536 iterations, but I wasn't patient enough to wait for it to finish. The time order is clearly O(N^2).

$i<<8>>8 is equal to $i, I just wrote it that way so that there was no bias due to the overhead of shifting the number.

<?php
ini_set('memory_limit', '20M');
ini_set('display_errors', 'on');
ini_set('max_execution_time', '0');

function utime() {
        $t = explode( " ", microtime() );
        return $t[0] + $t[1];
}

$iterations = 16384;

$a = array();
$t = utime();
for ($i=0; $i<$iterations; $i++) {
        $a[$i<<8>>8] = 0;
}
$t = utime() - $t;
print "Best case: {$t}s\n";

$a = array();
$t = utime();
for ($i=0; $i<$iterations; $i++) {
        $a[$i<<8<<8] = 0;
}
$t = utime() - $t;

print "Worst case: {$t}s\n";

?>

Results:

[2347][tstarling@srv31:~]$ php insert_speed.php
Best case: 0.0222568511963s
Worst case: 21.1022908688s

Another run with 65536 iterations on larousse:

[18:38][hashar@larousse(misc):~]$
Best case: 0.27304816246033s
Worst case: 733.47300195694s
[18:50][hashar@larousse(misc):~]$