You have N buckets, a hashing function for key => bucket #, and each bucket has a linked list of value pointers. You hash the key down to a bucket number, walk the list until you find your key, which will give you your value.
To get all the keys, you need to walk all the buckets' lists, which is O(n).
> they're obviously keeping track of the keys internally in an array to support the ordered hashes.
Which means that they can return them in an O(1) operation, but they choose not to for some reason.
Edit: I'm wrong- I just remembered why they can't return them, and it is because they're not storing the keys in an array. D'oh. They're using a doubly-linked list. So to return a list of keys you'd need to walk the linked list- an O(n) operation.
See: http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-h... for more info.