HashSet vs List vs Dictionary

Out of curiosity after reading some articles on how the HashSet<T> (introduced in .Net 3.5) class is more performant than the List<T> class for set operations, I set about doing some experiments of my own to get a feel of just how much faster a HashSet is, and under what circumstances.

Also, whilst there’s been much comparison between HashSet<T> and List<T>, I have found nothing on how HashSet<T> fares against Dictionary<TKey, TValue> in performance terms, so I’ll factor that into consideration too!

Using a HashSet, a List and a Dictionary of integer and a simple reference type, I ran the following tests:

Test 1: add 1000000 value type objects without checking for duplicates

Test 2: add 1000000 reference type objects without checking for duplicates

Test 3: run Contains() method against half the objects in a list of 10000 value type objects

Test 4: run Contains() method against half the objects in a list of 10000 reference type objects

Test 5: remove half the objects in a list of 10000 value types

Test 6: remove half the objects in a list of 10000 reference types

The objective is to find out:

• how the three constructs performs for each of these basic operations
• how the performance differs for value and reference types

Test Results

Test 1 and Test 2

The List type is the clear winner here, and no surprise really given that both HashSet and Dictionary ensures that that are no duplicated, what’s surprising though is how much more overhead you incur when dealing with reference types!

Test 3 and Test 4

They say hash lookups are fast and it’s no lie! Interestingly though, looking for a matching reference type in the values of a Dictionary proved to be much slower than doing the same thing in a List.

Test 5 and Test 6

The power of hash lookup strikes again!

Source Code

You can download the source code for the tests on here.

Parting Thoughts…

The results I posted here suggest that HashSet and Dictionary types are in general better performing than List whose faster speed at adding new items is greatly offset by deficits in other common operations. However, it’s important to remember that based on your use case the type of collection you should use normally picks itself – use a list if you just need a List to keep track of items; use a Dictionary if you require hash lookup against some value (an ID for your objects perhaps?); use a hash set if you need to perform set operations (e.g. set comparison, determine subset/superset relationship) frequently, and so on.

In practice, the difference in your application’s overall performance resulting from using a different collection type is trivial and should not dictate which collection type you use UNLESS proven otherwise via profiling!

Also, you should be mindful of other differences between the three types, both in terms of behaviour as well as functionalities, for instance:

• HashSet.Add will skip a new item if it’s deemed equal to one of the existing items and return false.
• Dictionary.Add will throw an exception if the new key being added is deemed equal to one of the existing keys. However, if you use the Dictionary‘s indexer instead, it will replace the existing item if the new item is deemed equal to it.
• List.Add will simply add the same item twice.
• HashSet provides some very useful methods such as IsSubsetOf and Overlaps, both can be achieved on the other collection types using LINQ but HashSet provides an optimized, ready-made solution