You can do it in XS and you can also do it by tying the hash, then providing FIRSTKEY and NEXTKEY. This is how, for instance, you can have a sorted hash. Look at Tie::Hash::Sorted (by our own Limbic~Region) for an example.
My criteria for good software:
Does it work?
Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Comment on Re: Perl level control of hash iterators