Tag Archives: hash tables

.NET collections and search times

I came across a question on stackoverflow.com on which is the fastest collection for finding if a string of equal value is contained in the collection.  It was correctly answered that a Hashset in .NET 3.5 and a Dictionary in .NET 2.0 would be the fastest collections for finding an exact string match, since they both run in O(1) time.

I was still interested in what the relative difference in times would be.  So I wrote a console application that created a list of 100K unique strings in 5 common collection types and than searched each of the collections for the 100K strings, recording the time for each collection to find them all.  Here are the results …

Trial 1: Trial 2: Trial 3:
NameValueCollection 82.1ms 78.9ms 79.7 ms
HashSet 23.8ms 24.9ms 24.3 ms
Dictionary 25.7ms 26.2ms 29.0 ms
List 1:03.985 min 1:20.637 min 1:04.39 min
Sorted List<string> w/ BinarySearch 199.9ms 210.0 ms 214.0 ms

As predicted the HashSet and Dictionary were the fastest, but is that the whole story?  What if we wanted to perform a case insensitive search, would the results be the same?  What is the performance impact of populating these collections?  How much memory do they use?

Much of the quicker lookup times of the key value based collections comes at the price of increased overhead in populating the collections as well larger memory footprint.