The only thing you're guaranteed is consistency between keys() and values(). Basically, don't ever count on keys being in order and you'll be OK.
From perldoc -f keys:
The keys 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 the same order as either the "values" or "each" function produces (given that the hash has not been modified). Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons (see "Algorithmic Complexity Attacks" in perlsec).