.NET Performance Improvements Series: List vs. Dictionary vs. HashSet 🚀

List vs Dictionary vs HashSet

Welcome to my .NET Performance Improvements Series! 🎉 In this series, we’ll explore various ways to enhance performance in C#. This post is the first in the series, where we compare List, Dictionary<TKey, TValue>, and HashSet, focusing on their performance in searching operations. Let’s dive in! 🏆

Meet the Contenders 🤼‍♂️

1. List — The Reliable Foot Soldier 🪖

A List is an ordered collection of elements, perfect for storing and iterating over items.

✅ Pros:

• Contiguous memory allocation → fast iteration
• Maintains insertion order
• Efficient Add() (O(1) amortized) and Index Access (O(1))

❌ Cons:

• Search is slow (O(n) — linear scan required)
• Insert/Delete in the middle → costly (O(n) due to shifting)

2. Dictionary<TKey, TValue> — The Speed Demon ⚡

A Dictionary<TKey, TValue> is like a well-organized filing cabinet. It provides key-value pairs for fast lookups.

✅ Pros:

• Super-fast lookups (O(1) time complexity — yes, please! 🚀)
• Optimized for key-based access
• Efficient for large datasets

❌ Cons:

• Higher memory usage (due to hash table overhead) 📦
• Keys must be unique
• Not ordered (if you care about order, this isn’t your guy!)

3. HashSet — The Bouncer at the Club 🕶️

A HashSet is an unordered collection of unique values, optimized for quick lookups.

✅ Pros:

• Fast lookups (O(1), just like Dictionary 🎯)
• No duplicates allowed (because it keeps things exclusive)
• Uses less memory than Dictionary (since no key-value pairs)

❌ Cons:

• No key-value pairs (if you need a value with your key, use a Dictionary!)
• No ordering

The Performance Showdown ⚔️

Now, let’s talk about the most critical factor: searching for an item in a collection.

Searching for an Item

• List: O(n) (scans one by one — very slow for large lists) 🐢
• Dictionary<TKey, TValue>: O(1) (direct access — super fast) 🚀
• HashSet: O(1) (same fast lookup as Dictionary) 🏎️

If your main goal is searching for an item in a large dataset, Dictionary<TKey, TValue> is the clear winner! 🏆🎉

Benchmarking (Because Science! 🧪)

Below are two benchmark tests performed to analyze search performance:

• Searching 10 items, all of which exist

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;

namespace BenchmarkTesting;

[MemoryDiagnoser]
[SimpleJob(runtimeMoniker: RuntimeMoniker.Net80, launchCount: 1, warmupCount: 0, iterationCount: 1)]
[SimpleJob(runtimeMoniker: RuntimeMoniker.Net90, launchCount: 1, warmupCount: 0, iterationCount: 1)]
public class CollectionBenchmark
{
    private List<Item> itemList;
    private Dictionary<int, Item> itemDict;
    private HashSet<Item> itemHashSet;
    private int[] searchIds;

    [GlobalSetup]
    public void Setup()
    {
        var random = new Random();
        itemList = new List<Item>();
        itemDict = new Dictionary<int, Item>();
        itemHashSet = new HashSet<Item>(new ItemComparer());

        for (int i = 0; i < 10000; i++)
        {
            var item = new Item
            {
                Id = i,
                Field1 = "Field1_" + i,
                Field2 = "Field2_" + i,
                Field3 = "Field3_" + i
            };
            itemList.Add(item);
            itemDict[item.Id] = item;
            itemHashSet.Add(item);
        }

        searchIds = new int[10];
        for (int i = 0; i < 10; i++)
        {
            searchIds[i] = random.Next(1000);
        }
    }

    [Benchmark]
    public void SearchInList()
    {
        foreach (var id in searchIds)
        {
            _ = itemList.Find(x => x.Id == id);
        }
    }

    [Benchmark]
    public void SearchInDictionary()
    {
        foreach (var id in searchIds)
        {
            _ = itemDict.TryGetValue(id, out _);
        }
    }

    [Benchmark]
    public void SearchInHashSet()
    {
        foreach (var id in searchIds)
        {
            _ = itemHashSet.TryGetValue(new Item { Id = id }, out _);
        }
    }
}

public class Item
{
    public int Id { get; set; }
    public string Field1 { get; set; }
    public string Field2 { get; set; }
    public string Field3 { get; set; }

    public override bool Equals(object obj)
    {
        return obj is Item item && Id == item.Id;
    }

    public override int GetHashCode()
    {
        return Id.GetHashCode();
    }
}

public class ItemComparer : IEqualityComparer<Item>
{
    public bool Equals(Item x, Item y)
    {
        return x.Id == y.Id;
    }

    public int GetHashCode(Item obj)
    {
        return obj.Id.GetHashCode();
    }
}

Summar

TL;DR — When to Use What? 🤔

+--------------------------+---------------------------------+
|        Collection        |            Best For             |
+--------------------------+---------------------------------+
| List                     | Ordered data, small datasets 📜 |
| Dictionary<TKey, TValue> | Fast lookups, key-value pairs ⚡|
| HashSet                  | Unique items, fast searches 🎯  |
+--------------------------+---------------------------------+

Final Verdict 🎤

If you need to search for an item efficiently, Dictionary<TKey, TValue> wins by a landslide! 🏆💨 It’s fast, efficient, and perfect for large datasets. But if you just need a simple list with ordering, stick with List. And if you want quick lookups without duplicate values, go with HashSet.

Stay tuned for more posts in the .NET Performance Improvements Series! 🚀🔥