HashSet vs List vs Dictionary

Out of curios­i­ty 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 cir­cum­stances.

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, TVal­ue> 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 val­ue type objects with­out check­ing for dupli­cates

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

Test 3: run Con­tains() method against half the objects in a list of 10000 val­ue 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 val­ue 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 oper­a­tions
  • how the per­for­mance dif­fers for val­ue and ref­er­ence types

Test Results

Test 1 and Test 2


The List type is the clear win­ner here, and no sur­prise real­ly giv­en that both Hash­Set and Dic­tio­nary ensures that that are no dupli­cat­ed, 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


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

Test 5 and Test 6


The pow­er of hash lookup strikes again!

Source Code

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

Parting Thoughts…

The results I post­ed here sug­gest that Hash­Set and Dic­tio­nary types are in gen­er­al bet­ter per­form­ing than List whose faster speed at adding new items is great­ly off­set by deficits in oth­er com­mon oper­a­tions. How­ev­er, it’s impor­tant to remem­ber that based on your use case the type of col­lec­tion you should use nor­mal­ly 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 val­ue (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­quent­ly, 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 pro­fil­ing!

Also, you should be mind­ful of oth­er 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­ev­er, if you use the Dic­tio­nary’s index­er 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 oth­er col­lec­tion types using LINQ but Hash­Set pro­vides an opti­mized, ready-made solu­tion