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.
insert 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).
Sorry 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.
