I had to look this up because I was thinking otherwise, but now I believe you are correct - it is just inconsistent between runs:

http://perldoc.perl.org/functions/each.html says "Hash entries are returned in an apparently random order. The actual random order is subject to change in future versions of Perl, but it is guaranteed to be in the same order as either the keys or values function would produce on the same (unmodified) hash. Since Perl 5.8.2 the ordering can be different even between different runs of Perl for security reasons (see Algorithmic Complexity Attacks in perlsec)."