6 ms·
Uh, here's how a hash table is commonly built. Ruby's may be optimized, but the jist is the same. You have N buckets, a hashing function for key => bucket #,
by lsb 18y ago
Uh, here's how a hash table is commonly built. Ruby's may be optimized, but the jist is the same.
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).
- subwindow 18y agoI'm perfectly aware of that, and if you read my comment you'll see that I acknowledge that fact. However, I also said: > 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-hash/ http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-h... for more info.