A quick benchmark seems to confirm this; asking an empty hash is much faster than asking a filled one, but the number of keys in the full hash seems to have no significant influence on the speed:

use strict;
use warnings;
use Benchmark qw(cmpthese);

for my $len (2..6) {
    our (%full, %empty);

    my $a = 'A';
    $full{$a++} = $a while length($a) < $len;

    print "\nLength $len with ", scalar(%full), "items\n";
    cmpthese -1, {
        full    => sub {die unless %full},
        empty    => sub {die if %empty},
    }
}
__END__
Length 2 with 22/32items
           Rate  full empty
full  1286220/s    --  -77%
empty 5481192/s  326%    --

Length 3 with 510/1024items
           Rate  full empty
full  1052183/s    --  -82%
empty 5748771/s  446%    --

Length 4 with 13961/32768items
           Rate  full empty
full   998734/s    --  -84%
empty 6056132/s  506%    --

Length 5 with 310721/524288items
           Rate  full empty
full   963764/s    --  -83%
empty 5681139/s  489%    --

Length 6 with 8655839/16777216items
           Rate  full empty
full   849541/s    --  -86%
empty 6124859/s  621%    --
[download]

Note that the number of hash items grows exponentially, while the number of iterations decreases linearly at best.