I usually want that when what I really need is ordering but for some reason I want key-based/random access to the values.

I think Ruby added this recently. I'm not using it yet. A crappy hack can just dump the next/prev key into the value, plus a pointer to the first, and drop them all in a hash. It's not really pretty, but would give you ordering if you want it. Another hack is to store just the keys in a sorted list and keep the values in the hash (but this is equally inelegant to the list+hash hack and it has the same maintenance overhead).

I think most of the ordered-hashes are implemented with something like list pointers between the hash keys, but then again I haven't looked too closely under that kimono.

Edit: trees are also a good compromise.