Out of curios­ity after read­ing some arti­cles on how the HashSet<T> (intro­duced in .Net 3.5) class is more per­for­mant than the List<T> class for set oper­a­tions, I set about doing some exper­i­ments of my own to get a feel of just how much faster a Hash­Set is, and under what circumstances.

Also, whilst there’s been much com­par­i­son between HashSet<T> and List<T>, I have found noth­ing on how HashSet<T> fares against Dictionary<TKey, TValue> in per­for­mance terms, so I’ll fac­tor that into con­sid­er­a­tion too!

Using a Hash­Set, a List and a Dic­tio­nary of inte­ger and a sim­ple ref­er­ence type, I ran the fol­low­ing tests:

Test 1: add 1000000 value type objects with­out check­ing for duplicates

Test 2: add 1000000 ref­er­ence type objects with­out check­ing for duplicates

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

Test 4: run Con­tains() method against half the objects in a list of 10000 ref­er­ence 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 ref­er­ence types

The objec­tive is to find out:

  • how the three con­structs per­forms for each of these basic operations
  • how the per­for­mance dif­fers for value and ref­er­ence types

Test Results

Test 1 and Test 2

image

The List type is the clear win­ner here, and no sur­prise really given that both Hash­Set and Dic­tio­nary ensures that that are no dupli­cated, what’s sur­pris­ing though is how much more over­head you incur when deal­ing with ref­er­ence types!

Test 3 and Test 4

image

They say hash lookups are fast and it’s no lie! Inter­est­ingly though, look­ing for a match­ing ref­er­ence type in the val­ues of a Dic­tio­nary proved to be much slower than doing the same thing in a List.

Test 5 and Test 6

image

The power of hash lookup strikes again!

Source Code

You can down­load the source code for the tests on here.

Part­ing Thoughts…

The results I posted here sug­gest that Hash­Set and Dic­tio­nary types are in gen­eral bet­ter per­form­ing than List whose faster speed at adding new items is greatly off­set by deficits in other com­mon oper­a­tions. How­ever, it’s impor­tant to remem­ber that based on your use case the type of col­lec­tion you should use nor­mally picks itself – use a list if you just need a List to keep track of items; use a Dic­tio­nary if you require hash lookup against some value (an ID for your objects per­haps?); use a hash set if you need to per­form set oper­a­tions (e.g. set com­par­i­son, deter­mine subset/superset rela­tion­ship) fre­quently, and so on.

In prac­tice, the dif­fer­ence in your application’s over­all per­for­mance result­ing from using a dif­fer­ent col­lec­tion type is triv­ial and should not dic­tate which col­lec­tion type you use UNLESS proven oth­er­wise via profiling!

Also, you should be mind­ful of other dif­fer­ences between the three types, both in terms of behav­iour as well as func­tion­al­i­ties, for instance:

  • HashSet.Add will skip a new item if it’s deemed equal to one of the exist­ing items and return false.
  • Dictionary.Add will throw an excep­tion if the new key being added is deemed equal to one of the exist­ing keys. How­ever, if you use the Dic­tio­nary’s indexer instead, it will replace the exist­ing item if the new item is deemed equal to it.
  • List.Add will sim­ply add the same item twice.
  • Hash­Set pro­vides some very use­ful meth­ods such as IsSub­setOf and Over­laps, both can be achieved on the other col­lec­tion types using LINQ but Hash­Set pro­vides an opti­mized, ready-made solution
Share

6 Responses to “HashSet vs List vs Dictionary”

  1. […] I do a fair bit of per­for­mance tests on ran­dom things that pique my inter­est, it’s only nat­ural that I should make the task of carrying […]

  2. Thanks for doing this. I was won­der­ing how Hash­Set stacks up against List. Now you’ve answered it.

  3. Fabio says:

    Cool! Thanks for the insight!

  4. Ruperto Leon says:

    Excel­lent, Thanks!

  5. Sagar says:

    Excel­lent arti­cle Sir, Thank you

  6. Andrew says:

    Nice and clear.

Leave a Reply