$ perldoc -f each
  each HASH
    Entries are returned in an apparently random order. [...] Since
    Perl 5.8.1 the ordering is different even between different
    runs of Perl for security reasons (see "Algorithmic Complexity
    Attacks" in perlsec).
[download]

Great feature, so let's try it!

$ PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299; print $_ for each %a' 
+| md5sum
HASH_SEED = 3379561142
b6d67a24906e8a8541291882f81d31ca  -
$ PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299; print $_ for each %a' 
+| md5sum
HASH_SEED = 4068799219
b6d67a24906e8a8541291882f81d31ca  -
[download]

Hmm, same MD5? And what about keys and values?

$ PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299; print $_ for keys %a' 
+| md5sum
HASH_SEED = 1151419008
dd56233cf84603df0d47d272da1af003  -
$ PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299; print $_ for keys %a' 
+| md5sum
HASH_SEED = 2731377116
dd56233cf84603df0d47d272da1af003  -

$ PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299; print $_ for values %a
+' | md5sum
HASH_SEED = 1861095523
c1a75ab8e3bf1ff6c07b01025a1219e9  -
$ PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299; print $_ for values %a
+' | md5sum
HASH_SEED = 788024661
c1a75ab8e3bf1ff6c07b01025a1219e9  -
[download]

This implies I'm always getting the same output, so each, keys and values are returning the elements in the same order even when the seeds are different! My Perl was compiled without -DUSE_HASH_SEED_EXPLICIT (according to $Config::Config{ccflags}) so I shouldn't be setting the seed manually but anyway I tried, just in case. I used bash's $RANDOM variable, that returns a different value each time it's evaluated:

$ echo $RANDOM
8035
$ echo $RANDOM
797
$ PERL_HASH_SEED=$RANDOM PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299;
+ print $_ for values %a' | md5sum
HASH_SEED = 26815
c1a75ab8e3bf1ff6c07b01025a1219e9  -
$ PERL_HASH_SEED=$RANDOM PERL_HASH_SEED_DEBUG=1 perl -e 'my %a=0..299;
+ print $_ for values %a' | md5sum
HASH_SEED = 30449
c1a75ab8e3bf1ff6c07b01025a1219e9  -
[download]

Super Search found this but it doesn't seem to apply here since perl -V | grep SEED shows nothing. The test here also returns the same output every time I run it. This is a 5.8.8 running on Debian/Linux. Ideas?