First article of the year! I’ve been busy preparing for Confoo here in Montreal, so I haven’t had much time lately for focusing on my blog, unfortunately.

Today I just wanted to showcase (again</a>) how important it is to know your data structures. This time, I wrote a small benchmark measuring lookup performance between Dictionary, SortedList, SortedDictionary and HashSet.

These classes offer more or less the same interface but are clearly solving different problems. When it’s necessary to store and perform lookups in large volumes, it’s good to know how they’re behaving.

You can find the code along with the results on GitHub.

As we can see, Dictionary is the clear winner, but it depends on the use case. If, like here, we’re only interested into lookups, then Dictionary is the right approach. Or HashSet if you don’t need to store key/value pairs.

In case instead the order of keys is important, the Sorted___ classes are the way to go.

The reason for this big gap in the results is due to the different data structures used internally:

• SortedDictionary is a binary search tree with O(log n) retrieval
• SortedList is a wrapper over an array of key/value pairs with O(log n) retrieval

Both Dictionary and HashSet instead exhibit constant lookup complexity ( O(1) ), therefore leading to better overall performance.

Did you like this post? Then