要素数が大きくなると遅くなる？

お隣日記のコメントから。コメントの投稿者は id:n314 さんかな？

PHPの配列って、Hashだったんですか？
ただの連想配列かと思ってました。

PHPのソース拝んでいないので、実際のことはわからないけど、データ数が多くなると、ムチャクチャ遅くなるので、線形探索してんじゃないの？って思ってます。

え？PHPの array が要素数が大きくなると遅くなるなんて話は聞いたことがないなぁ。つうか、実際ソースを見る限り Hash Table なんだけどな。
一応ベンチマーク。

<?php
require_once 'Benchmark/Timer.php';

function test_search($array, $n) {
    $size = count($array);
    $sum = 0;

    for ($i = 0; $i < $n; $i++) {
        $index = rand(0, $size - 1);
        $sum += $array[$index];
    }
}

function test_add(&$array, $n) {
    for ($i = 0; $i < $n; $i++) {
        $array[] = rand();
    }
}

function main() {
    $target_100 = range(1, 100);
    $target_10000 = range(1, 10000);
    $n = 1000;

    $timer = new Benchmark_Timer();
    $timer->start();

    test_search($target_100, $n);
    $timer->setMarker('search 100');

    test_search($target_10000, $n);
    $timer->setMarker('search 10000');

    test_add($target_100, $n);
    $timer->setMarker('add 100');

    test_add($target_10000, $n);
    $timer->setMarker('add 10000');

    $timer->stop();
    $timer->display();
}

main();
?>

% php bench_array.php
-----------------------------------------------------------
marker         time index            ex time         perct
-----------------------------------------------------------
Start          1162010125.80803800   -                0.00%
-----------------------------------------------------------
search 100     1162010125.81098700   0.002949        31.00%
-----------------------------------------------------------
search 10000   1162010125.81389500   0.002908        30.57%
-----------------------------------------------------------
add 100        1162010125.81577900   0.001884        19.80%
-----------------------------------------------------------
add 10000      1162010125.81753100   0.001752        18.42%
-----------------------------------------------------------
Stop           1162010125.81755100   0.000020         0.21%
-----------------------------------------------------------
total          -                     0.009513       100.00%
-----------------------------------------------------------

やっぱり、データが多いからって遅くなるってことはないな。
つか、どこから要素数が多くなると遅くなるなんて話を持ってきたんだろ。array_search とか in_array の話？それなら確かに線形時間がかかると思うけど。
関係ないけど、「データが多い」でも、「データ数が大きい」でもなく、「データ数が多い」って日本語おかしくない？