So, if I understand correctly, the code you posted is visibly broken and has been for a very long time.

Well yes, it is broken, that was my point for bringing it up :-). Whether it is visibly broken or not depends on whether you have any collisions. In the case you posted there are two sets of collisions, 4 and 1, and 3 and 0. (You can tell because they reverse each copy in earlier perls.) However if changed it to be 1,2,3,5,7,8 you would not have any collisions and the order would appear the same. Eg try:

my %hash = map { $_ => 1 } (1,2,3,5,7,8);
[download]

In 5.18 the order will be different for every hash. No exceptions. Here is what perlfunc will say in 5.18:

Hash entries are returned in an apparently random order.  The actual r
+andom
order is specific to a given hash; the exact same series of operations
on two hashes may result in a different order for each hash. Any inser
+tion
into the hash may change the order, as will any deletion, with the exc
+eption
that the most recent key returned by C<each> or C<keys> may be deleted
without changing the order. So long as a given hash is unmodified you 
+may
rely on C<keys>, C<values> and C<each> to repeatedly return the same o
+rder
as each other. See L<perlsec/"Algorithmic Complexity Attacks"> for
details on why hash order is randomized. Aside from the guarantees
provided here the exact details of Perl's hash algorithm and the hash
traversal order are subject to change in any release of Perl.
[download]