But the main problem with your benchmark is that by pushing the code under test inside a subroutine, the mechanics of calling the subroutine, unpacking the parameters, and allocating memory to accumulate the results; all combine to entirely swamp the actual thing you are trying to test.

Adding a direct test of each of the two possibilities to your benchmark dramatically shows up the cost of all that indirection, as well as confirming your original suspicion that arrays are 37% faster than hashes:

use strict;
use warnings;
use Benchmark;
use List::Util qw(shuffle);

my $count=5000000;

my @existing_indexes    = ( 5,6,8..53,62..106);
our @indexes = (0..200);

our @shuffled_indexes = shuffle @indexes;

our %test_hash;
our @test_array;

@test_array[ @existing_indexes ] = ();
@test_hash{  @existing_indexes } = ();



Benchmark::cmpthese( -1, {
    AviaSub => q{
        my $val = &arrayLookup( \@test_array, \@indexes );
    },
    HviaSub  => q{
        my $val = &hashLookup(  \%test_hash,  \@indexes );
    },
    AviaSubS => q{
        my $val = &arrayLookup( \@test_array, \@shuffled_indexes );
    },
    HviaSubS  => q{
        my $val = &hashLookup(  \%test_hash, \@shuffled_indexes )
    },
    Adirect  => q{
        my $count = 0;
        exists $test_array[ $_ ] and ++$count for @indexes;
    },
    Hdirect  => q{
        my $count = 0;
        exists $test_hash{ $_ } and ++$count for @indexes;
    },
} );




sub arrayLookup {
    my $array   = shift;
    my $indexes = shift;

    my @results = map {
        exists $array->[$_];
    } @$indexes;

    return \@results;
}

sub hashLookup {
    my $hash = shift;
    my $keys = shift;

    my @results = map {
        exists $hash->{$_};
    } @$keys;

    return \@results;
}
[download]

The results:

c:\test>junk3
            Rate  HviaSub HviaSubS  AviaSub AviaSubS  Hdirect  Adirect
HviaSub   2085/s       --      -1%      -2%      -5%     -85%     -89%
HviaSubS  2113/s       1%       --      -1%      -4%     -85%     -89%
AviaSub   2131/s       2%       1%       --      -3%     -85%     -89%
AviaSubS  2203/s       6%       4%       3%       --     -84%     -89%
Hdirect  14147/s     578%     569%     564%     542%       --     -27%
Adirect  19366/s     829%     816%     809%     779%      37%       --
[download]