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).
Any feedback is really welcomed, for instance, do you know of better data structures to do the work? I'm using a red black tree and an hash table. The pastie above documents the specification more or less. Thanks