I am building the hash in the test, but I left the construction of the array outside of it:

use Benchmark qw{ timeit timediff timestr };

use strict;
my @array;

for (1 .. 10) {
    push(@array, $_);
    my $time = timeit(500000, "&search_array($_)");
    my $time2 = timeit(500000, "&search_hash($_)");

    printf("%2d  %s\n", $_, timestr timediff($time, $time2));
}

sub search_array {
    my $max = shift;
    my $item;
    my $looking = int(rand($max));

    foreach $item (@array) {
        return 1 if $item == $looking;
    }
    return;
}

sub search_hash {
    my $max = shift;

    my %hash;
    @hash{@array} = ();

    return 1 if exists $hash{rand($max)};
    return;
}
[download]

Actually this sucks. I made some stuff more readable and my results now differ from what I was seeing earlier. I can't reproduce my old results. So yah, it looks like you're right. It's an increasing trend in favor of a linear search. My bad.