6 ms·
Why not use a hashtable with a linked list running through it (basically the python ordered dictionary class without the mapping). I believe ruby 1.9 uses thes
by kingkilr 17y ago
Why not use a hashtable with a linked list running through it (basically the python ordered dictionary class without the mapping). I believe ruby 1.9 uses these for its default hash type.
- antirez 17y agoinsert in order inside a linked list is O(N), or I missed something? Maybe they are using some more advanced kind of linked list where it's possible to run a binary search (like skip lists or alike).
- kingkilr 17y agoSorry this assumes that you wanted consistent ordering, not necessarily that you want to be able to create arbitrary ordering for it. So you'd have insert ordering.