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.
The Code Nose 