561

It's clear that a search performance of the generic HashSet<T> class is higher than of the generic List<T> class. Just compare the hash-based key with the linear approach in the List<T> class.

However calculating a hash key may itself take some CPU cycles, so for a small amount of items the linear search can be a real alternative to the HashSet<T>.

My question: where is the break-even?

To simplify the scenario (and to be fair) let's assume that the List<T> class uses the element's Equals() method to identify an item.

1
  • 9
    If you really want to minimize lookup time, also consider arrays and sorted arrays. To answer properly this question, a benchmark is needed, but you need to tell us more about T. Also, HashSet performance can be affected by the running time of T.GetHashCode(). Commented Apr 14, 2012 at 8:36

12 Answers 12

1055

A lot of people are saying that once you get to the size where speed is actually a concern that HashSet<T> will always beat List<T>, but that depends on what you are doing.

Let's say you have a List<T> that will only ever have on average 5 items in it. Over a large number of cycles, if a single item is added or removed each cycle, you may well be better off using a List<T>.

I did a test for this on my machine, and, well, it has to be very very small to get an advantage from List<T>. For a list of short strings, the advantage went away after size 5, for objects after size 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Here is that data displayed as a graph:

enter image description here

Here's the code:

static void Main(string[] args)
{
    int times = 10000000;

    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");

        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];
        
        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");

        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}
12
  • 12
    Thank you so much! This is a great explanation, I was looking for something that could add and remove faster than a List<T> for a game engine, and since I will usually have a high volume of objects, this kind of a collection would be perfect. Commented Jun 4, 2013 at 19:08
  • 37
    There is actually a collection in the .NET framework that switches between a list and hastable implementation depending on the number of items it contains: HybridDictionary.
    – MgSam
    Commented Nov 1, 2013 at 2:12
  • 12
    MS seems to have abandoned it thought, as it has only a non-generic version available.
    – MgSam
    Commented Nov 1, 2013 at 2:14
  • 85
    As full as this answer is, it fails to answer the original question regarding list vs hashset search performance. You are testing how quickly you can insert and remove from them, which takes considerably more time and different performance characteristics than search. Try again, using .Contains, and your graph will change significantly. Commented Apr 1, 2015 at 19:43
  • 8
    @hypehuman the CPU cannot work directly on data in the system memory but pulls in data from the memory into its cache to work on. There is a significant delay between the request for memory to be moved and the memory actually arriving so the CPU will often request a larger chunk of contiguous memory to be moved at once. The idea behind this is that the memory needed by the next instruction is probably very near to the memory used by the previous instruction and thus is often already in the cache. When your data is scattered all over the memory the chance of getting lucky is reduced.
    – Roy T.
    Commented Jan 5, 2016 at 13:45
121

It's essentially pointless to compare two structures for performance that behave differently. Use the structure that conveys the intent. Even if you say your List<T> wouldn't have duplicates and iteration order doesn't matter making it comparable to a HashSet<T>, its still a poor choice to use List<T> because its relatively less fault tolerant.

That said, I will inspect some other aspects of performance,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)     | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)*    | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

* Even though addition is O(1) in both cases, it will be relatively slower in HashSet since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.

6
  • 32
    My question (six years ago) was not about the theoretical performance. Commented Jun 4, 2014 at 9:25
  • 1
    HashSet does allow random access with ElementAt(), and I think that would be O(n) time. Also, perhaps you could put in your table whether each collection allows duplicates (e.g: lists do, but hashsets don't).
    – Dan W
    Commented Oct 6, 2015 at 21:38
  • 1
    @DanW in the table I'm comparing purely performance, not behavioral characteristics. Thanks for ElementAt tip.
    – nawfal
    Commented Oct 7, 2015 at 22:29
  • 1
    ElementAt is just a LINQ extension.. it does nothing you can't do and optimize better in another method you add yourself. I think the table made more sense without considering ElementAt since all the other methods exist on those classes explicitly.
    – Dinerdo
    Commented Nov 23, 2018 at 5:01
  • 1
    Thanks for this table, in my use case I need to add and remove targets to a populated collection each time they are enabled / disabled and this helped me make the right choice (HashSet). Commented May 26, 2020 at 8:57
82

You're looking at this wrong. Yes a linear search of a List will beat a HashSet for a small number of items. But the performance difference usually doesn't matter for collections that small. It's generally the large collections you have to worry about, and that's where you think in terms of Big-O. However, if you've measured a real bottleneck on HashSet performance, then you can try to create a hybrid List/HashSet, but you'll do that by conducting lots of empirical performance tests - not asking questions on SO.

5
  • 6
    large collections you have to worry about. We can redefine that question in terms when small collection becomes large enough to worry about HashSet vs List? tens, tens of thousands, billions of elements?
    – om-nom-nom
    Commented Jan 24, 2012 at 18:45
  • 13
    No, you'll see considerable performance difference above a few hundred elements. The point is always use a HashSet if you're doing the types of accesses that HashSet is good at (e.g. is element X in the set.) If your collection is so small that a List is faster then it is very rare that those lookups are actually a bottleneck in your application. If you can measure it to be one, fine you can try to optimize it - but otherwise you're wasting your time.
    – Eloff
    Commented Jan 24, 2012 at 20:31
  • 27
    What if you have a small collection that is hit many times in a loop? That's not an uncommon scenario.
    – dan-gph
    Commented Jun 18, 2014 at 10:01
  • 8
    @om-nom-nom - I think the point is that it doesn't matter where the tipping point is, because: "If performance is a worry, use HashSet<T>. In the small-number cases where List<T> might be faster, the difference is insignificant." Commented Jun 14, 2015 at 21:49
  • ...really could rephrase that as "whenever an item is accessed thousands of times per second, profile it". There are plenty of cases where HashSet is "slow" relatively speaking, I guess it depends on whether or not you work in a domain where "thousands of times per second" is a common thing (loaded servers or computational algorithms) but then it's also somewhat more probable that what you really want is an array, since the JIT has an easier time optimizing IL for arrays (because guarantees such as non-mutation of state over a span of code is harder to prove for list, and very useful if true).
    – AnorZaken
    Commented Mar 20 at 12:00
61

Whether to use a HashSet<> or List<> comes down to how you need to access your collection. If you need to guarantee the order of items, use a List. If you don't, use a HashSet. Let Microsoft worry about the implementation of their hashing algorithms and objects.

A HashSet will access items without having to enumerate the collection (complexity of O(1) or near it), and because a List guarantees order, unlike a HashSet, some items will have to be enumerated (complexity of O(n)).

3
  • List potentially might calculate offset for the specific element by it's index (because all elements are the same type and potentially occupy same memory size). So List is not necessary enumerates it's elements Commented Oct 21, 2014 at 11:54
  • @Lu55 - The question is about searching for an item in a collection. A typical scenario is that the collection is dynamic - items may have been added or deleted since the last time you looked for a given item - so an index is not meaningful (because it will have changed). If you have a static collection (that won't change while you perform your calculations), or items are never deleted, and are always added at the end, then a List is preferred, because you can remember an index - that is the situation you are describing. Commented Nov 23, 2018 at 10:50
  • You can use a SortedSet if you need to sort a HashSet. Still much faster than a List.
    – live-love
    Commented Apr 19, 2020 at 18:10
38

Just thought I'd chime in with some benchmarks for different scenarios to illustrate the previous answers:

  1. A few (12 - 20) small strings (length between 5 and 10 characters)
  2. Many (~10K) small strings
  3. A few long strings (length between 200 and 1000 characters)
  4. Many (~5K) long strings
  5. A few integers
  6. Many (~10K) integers

And for each scenario, looking up values which appear:

  1. In the beginning of the list ("start", index 0)
  2. Near the beginning of the list ("early", index 1)
  3. In the middle of the list ("middle", index count/2)
  4. Near the end of the list ("late", index count-2)
  5. At the end of the list ("end", index count-1)

Before each scenario I generated randomly sized lists of random strings, and then fed each list to a hashset. Each scenario ran 10,000 times, essentially:

(test pseudocode)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Sample Output

Tested on Windows 7, 12GB Ram, 64 bit, Xeon 2.8GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]
7
  • 8
    Interesting. Thanks for running this. Sadly, I suspect these discussions trigger needless refactorings. Hopefully the takeaway for most people is that in your absolute worst case scenario, List still takes only 0.17 milliseconds to perform a single lookup, and is not likely going to require a substitution for HashSet until the lookup frequency reaches absurd levels. By then, the use of List usually is the least of the problems.
    – Paul Walls
    Commented Dec 10, 2012 at 5:12
  • This is not actual information for now.. Or maybe it is originally wrong... I just checked small values from 2 to 8 chars. List / HashSet were created for each 10 values... HashSet slower for 30%... If capacity in List is used then difference even ~40%. HashSet becomes faster for 10% only if we List is without specified capacity and checks each value before adding through whole list.
    – Maxim
    Commented Jun 28, 2017 at 20:52
  • If items count reduced to 4 then List again wins even in worst scenario (with 10% difference). So I do not recommend to use HashSet for small collection of strings (let's say < 20). And it is what is different from your "few small" tests.
    – Maxim
    Commented Jun 28, 2017 at 21:00
  • 1
    @Maxim can't really say my results are "wrong" -- it's what happened on my machine. YMMV. In fact, I just ran them again (gist.github.com/zaus/014ac9b5a78b267aa1643d63d30c7554) on a new Win10 4.0GHz 16GB solid state computer and got similar results. The takeaway I see is that the hashset performance was more consistent no matter where the search key was or how big the list, while list performance varied wildly from better to more than 300x slower. But as PaulWalls initially commented we're talking serious #microoptimization.
    – drzaus
    Commented Jun 30, 2017 at 16:20
  • @Maxim for reference: dotnetfiddle.net/5taRDd -- feel free to play around with it.
    – drzaus
    Commented Jun 30, 2017 at 16:39
14

The breakeven will depend on the cost of computing the hash. Hash computations can be trivial, or not... :-) There is always the System.Collections.Specialized.HybridDictionary class to help you not have to worry about the breakeven point.

2
  • 1
    You also need to take into account the cost of doing a comparison. In the case of Contains(T) the HashSet will do a comparison to check it doesn't have a Hash collision versis the List doing a Comparison on every item it looks at before it finds the correct one. You also have to take into account the distribution of the Hashes generated by T.GetHashCode() as if this always returns the same value you are basically making HashSet do the same thing as List. Commented Jul 9, 2012 at 9:26
  • Re "on the cost of computing the hash" - under what circumstances is this substantially more than the cost of comparing two items directly? Unless badly written, It will be a small multiple of the comparison cost. Hence in all "usual" circumstances, the break-even point happens at a small number of items. Commented Jul 17, 2021 at 14:50
9

You can use a HybridDictionary which automaticly detects the breaking point, and accepts null-values, making it essentialy the same as a HashSet.

1
  • 3
    Upvoted this for the idea, but nobody please ever use this today. Say no to non-generics. Also a dictionary is a key-value mappings, set is not.
    – nawfal
    Commented May 29, 2014 at 19:27
6

The answer, as always, is "It depends". I assume from the tags you're talking about C#.

Your best bet is to determine

  1. A Set of data
  2. Usage requirements

and write some test cases.

It also depends on how you sort the list (if it's sorted at all), what kind of comparisons need to be made, how long the "Compare" operation takes for the particular object in the list, or even how you intend to use the collection.

Generally, the best one to choose isn't so much based on the size of data you're working with, but rather how you intend to access it. Do you have each piece of data associated with a particular string, or other data? A hash based collection would probably be best. Is the order of the data you're storing important, or are you going to need to access all of the data at the same time? A regular list may be better then.

Additional:

Of course, my above comments assume 'performance' means data access. Something else to consider: what are you looking for when you say "performance"? Is performance individual value look up? Is it management of large (10000, 100000 or more) value sets? Is it the performance of filling the data structure with data? Removing data? Accessing individual bits of data? Replacing values? Iterating over the values? Memory usage? Data copying speed? For example, If you access data by a string value, but your main performance requirement is minimal memory usage, you might have conflicting design issues.

4

It depends. If the exact answer really matters, do some profiling and find out. If you're sure you'll never have more than a certain number of elements in the set, go with a List. If the number is unbounded, use a HashSet.

3

Depends on what you're hashing. If your keys are integers you probably don't need very many items before the HashSet is faster. If you're keying it on a string then it will be slower, and depends on the input string.

Surely you could whip up a benchmark pretty easily?

3

One factor your not taking into account is the robustness of the GetHashcode() function. With a perfect hash function the HashSet will clearly have better searching performance. But as the hash function diminishes so will the HashSet search time.

1

Depends on a lot of factors... List implementation, CPU architecture, JVM, loop semantics, complexity of equals method, etc... By the time the list gets big enough to effectively benchmark (1000+ elements), Hash-based binary lookups beat linear searches hands-down, and the difference only scales up from there.

Hope this helps!

1
  • 2
    JVM... or CLR :-)
    – bvgheluwe
    Commented May 31, 2017 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.