You can use a third-party dictionary or associative array implementation that provides deterministic orderings, such as Hash::Ordered.

$ demo() {
   perl -e'
      use v5.18;
      use Hash::Ordered qw( );
      my $h = Hash::Ordered->new();
      $h->set( $_, 1 ) for "a".."z";
      say $h->keys;
   '
}

$ demo
abcdefghijklmnopqrstuvwxyz

$ demo
abcdefghijklmnopqrstuvwxyz
[download]

You'd have to replace not just %hash, but the hashes referenced by the values of %hash.