Efficient way to get a range of Keys from Dictionary

Question

I have a Dictionary that for most operations I just need to retrieve a single entry by key, but for a few operations I will need to work with the entries associated with a range of keys. The way that occurs to me to do this is to use GetKeys and a FindAll that will match the range I am interested in, but was wondering if someone could suggest a better method.

Answer 1

A Dictionary which is implemented as a hash table is not particularly suited to efficiently perform range selection operations on keys. You'll have to visit all keys to find all of them in a specified range. A nice way to accomplish it is to query its collection of keys with a simple LINQ expression.

Answer 2

A SortedList or SortedDictionary would have the items sorted so you can try to get the key at the bottom of your range then traverse the elements to the top of your range.

Using binary search on a SortedList will give you the index of the key matching the bottom of your range, or the nearest higher value. See How to perform a binary search on IList<T>?