The order in which keys are returned by keys/each/value are supposed to be random (not crypotgraphically random, but explicity coded as random, with the random factor being different for each run (see PERL_HASH_SEED).

Uh, it may be different each time you run the script, but if you iterate through the same hash twice in your script, you'll get the same order twice.