Perl has 3 ways to iterate over a hash: "keys", "values", and "each". The first two do what you'd think; "each" in array context iterates over key/value pairs. All three return their results in an "apparently random" order.
You can also use "for" to iterate over a hash, same as you would over an array, but in that case the hash is converted to a list of alternating keys and values, which isn't as useful.
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)."
You can also use "for" to iterate over a hash, same as you would over an array, but in that case the hash is converted to a list of alternating keys and values, which isn't as useful.
[edited to correct a typo]