C#: Dictionary sorted on key with ~O(1) lookup

Question

didn't find an answer to this.

I like KeyedCollection, because it keeps the insertion order and has ~O(1) key lookup times.

Now I am looking for a similar type that will sort on the key instead of the insertion order.

SortedDictionary does exactly that, however the implementation is exactly the opposite of what I want. Inserts are O(1), lookups O(log n). However, I would like lookups ~O(1) (e.g. hash table) and the inserts can be O(log n) (binary tree?).

Does this exist? Shouldn't be hard implementation wise...

Thanks

Answer 1

There is no data structure in the .NET BCL that provides what you're looking for. Maybe there are 3rd party solutions out there.

In most cases, O(log n) will be sufficient. You might be micro-optimizing if you try to implement your own data structure.

However, the quickest way to do so might be by simply declaring a new class that has both a Dictionary and a SortedDictionary as private members. For all read methods, you'd choose the more efficient dictionary to return a value. For all write methods, you would handle both inner dictionaries and be careful that they'd stay in sync. This might be not the most memory efficient approach though. But if you like to optimize here, you'd have to re-implement most functionality of a hashtable.