|Just another Perl shrine|
When you obtain the list of keys or values from a hash, you no longer have a hash. You have a list, which has an intrinsic order. The mechanism for extracting that list from the hash must traverse the internal data structures in some order to produce the list, but that sequence is explicitly undefined. That is the essence of being unordered.
It makes no sense to say "A hash could return its values in the same order as an array." The statement presupposes that you can predict the order of the list of keys. You can't do that.
If your collection imposes a predictable ordering on the indexes/keys, you can iterate over it directly. Iteration relies on order. That's why iterating over the contents of a hash requires helper functions to manage it. Something has to convert the set of key-value pairs into a list. The resulting list may be invisible to the user (as in each()), or explicitly returned (keys(), values()), but it's there. Saying (%foo) also converts the hash into a list. It's no longer a hash at that point.
Operations over collections, whether ordered or not, may wish to impose an externally defined ordering on a list of the data. That is independent of whether the collection itself is intrinsically ordered. If you want your collection to maintain the data in a specific order, you are stuck with an array, if you intend to use basic Perl data structures. Linked lists and the like are outside the scope of this discourse. Alternately, you impose the desired order on a list each time you generate the list.
To an extent, it really is that simple.
In reply to Re^9: What makes an array sorted and a hash unsorted?