C# Collections Performance: List vs Dictionary vs HashSet

Master C# collections performance: List vs Dictionary vs HashSet vs Queue with Big-O tables, real benchmarks, and code examples. Pick the right one today.

Choosing the right data structure is one of the highest-leverage performance decisions you can make in .NET — and C# collections are where most of those decisions happen. Should you use a List<T> or a Dictionary<TKey, TValue>? When does a HashSet<T> beat both? And where does Queue<T> fit in? In this guide, we'll compare the four most-used collections in C# with Big-O complexity tables, runnable benchmark code, and clear rules for when to use each. By the end, you'll be able to justify your collection choice in a code review — not just guess.

Why C# Collections Performance Matters

Every collection type in .NET makes a trade-off. List<T> gives you cheap indexed access and great iteration speed but slow lookups by value. Dictionary<TKey, TValue> gives you near-instant lookups by key but uses more memory and has no meaningful ordering guarantees. Picking the wrong one rarely breaks your code — it silently makes it 10x, 100x, or 1000x slower as your data grows.

Here's the classic example. This code looks innocent:

// O(n * m) — a hidden nested loop
var activeUsers = allUsers
    .Where(u => activeUserIds.Contains(u.Id)) // List<int>.Contains is O(n)
    .ToList();

If activeUserIds is a List<int> with 50,000 entries and allUsers has 100,000 entries, that's up to 5 billion comparisons. Change one line and it becomes effectively linear:

var idSet = new HashSet<int>(activeUserIds);   // build once: O(m)
var activeUsers = allUsers
    .Where(u => idSet.Contains(u.Id))          // HashSet.Contains is O(1)
    .ToList();

That's the entire thesis of this article in two code blocks: the collection you choose defines the complexity of every operation you run against it. Now let's look at each collection properly.

Big-O Cheat Sheet: List vs Dictionary vs HashSet vs Queue

• List<T> — Access by index: O(1) · Search by value: O(n) · Add to end: O(1) amortized · Insert/Remove at position: O(n)
• Dictionary<TKey, TValue> — Lookup by key: O(1) · Add: O(1) amortized · Remove: O(1) · Search by value: O(n)
• HashSet<T> — Contains: O(1) · Add: O(1) amortized · Remove: O(1) · No duplicates, no indexing
• Queue<T> — Enqueue: O(1) amortized · Dequeue: O(1) · Peek: O(1) · Search: O(n)

"Amortized O(1)" means the operation is constant time on average: occasionally the collection must resize its internal array (doubling capacity and copying elements), but spread across many adds, the cost per add stays constant. This detail matters for the capacity tips in the best-practices section below.

List<T>: The Default Workhorse

List<T> is a dynamic array. Its elements sit in one contiguous block of memory, which makes it extremely CPU-cache-friendly — iterating a list is about as fast as .NET code gets.

var orders = new List<Order>(capacity: 10_000); // pre-size when you know the count

orders.Add(new Order { Id = 1, Total = 99.95m });

Order first = orders[0];          // O(1) — direct index access
decimal sum = 0;
foreach (var o in orders)         // fast, cache-friendly iteration
    sum += o.Total;

Why it's fast: indexed access is a single pointer offset calculation. Why it's slow: Contains, IndexOf, Find, and Remove(item) must scan every element until they find a match — O(n). Insert(0, item) is even worse: it shifts every existing element one slot to the right.

Use List<T> when: you mostly iterate, access by index, or append to the end. It should be your default collection — until you find yourself searching it repeatedly.

Dictionary<TKey, TValue>: O(1) Lookups by Key

A Dictionary is a hash table. It runs each key through GetHashCode(), uses the hash to jump straight to a bucket, and checks the handful of entries there with Equals(). That's why lookup cost doesn't grow with the number of items.

var productsBySku = new Dictionary<string, Product>
{
    ["SKU-001"] = new Product("Keyboard", 49.99m),
    ["SKU-002"] = new Product("Mouse", 29.99m)
};

// The right way to read: one hash lookup, no exception on miss
if (productsBySku.TryGetValue("SKU-001", out var product))
    Console.WriteLine($"{product.Name}: {product.Price:C}");

// Avoid this pattern — it hashes the key TWICE:
if (productsBySku.ContainsKey("SKU-001"))
    product = productsBySku["SKU-001"];

Prefer TryGetValue over the ContainsKey-then-indexer pattern: it performs one lookup instead of two, and it never throws KeyNotFoundException.

Use Dictionary when: you repeatedly look items up by a unique key — user by ID, product by SKU, config by name, cache by URL. If you've ever written list.FirstOrDefault(x => x.Id == id) inside a loop, you wanted a dictionary.

// Convert a list into a lookup structure once, then query it cheaply
Dictionary<int, User> usersById = users.ToDictionary(u => u.Id);

HashSet<T>: Fast Membership and Uniqueness

HashSet<T> is a dictionary with no values — just hashed keys. It answers exactly two questions extremely well: "Have I seen this before?" and "Is this item in the set?"

var seenEmails = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

foreach (var signup in signups)
{
    // Add returns false if the item already exists — check and insert in ONE operation
    if (!seenEmails.Add(signup.Email))
        Console.WriteLine($"Duplicate signup: {signup.Email}");
}

Note the Add return value: you don't need a separate Contains check before adding. Also note the StringComparer — passing a comparer to the constructor is how you get case-insensitive sets and dictionaries without normalizing strings everywhere.

HashSet also gives you set algebra that would be painful and slow with lists:

var admins  = new HashSet<int> { 1, 2, 3, 4 };
var editors = new HashSet<int> { 3, 4, 5, 6 };

admins.Overlaps(editors);                 // true — any shared members?
var both = new HashSet<int>(admins);
both.IntersectWith(editors);              // { 3, 4 }

Use HashSet when: you need uniqueness, fast Contains, or set operations — and you don't need indexing, ordering, or an associated value.

Queue<T>: First-In, First-Out Processing

Queue<T> is a circular buffer that processes items in arrival order. Both ends are O(1), which is exactly what a List can't give you — list.RemoveAt(0) shifts every remaining element and is O(n) per removal.

var jobs = new Queue<PrintJob>();
jobs.Enqueue(new PrintJob("report.pdf"));
jobs.Enqueue(new PrintJob("invoice.pdf"));

while (jobs.TryDequeue(out var job))      // safe: no exception when empty
    Console.WriteLine($"Printing {job.FileName}");

Use Queue when: order of arrival matters — job pipelines, breadth-first traversal, message buffering, rate-limited work. For producer/consumer scenarios across threads, use System.Threading.Channels or ConcurrentQueue<T> instead; plain Queue<T> is not thread-safe. And if you need priority ordering rather than arrival ordering, .NET 6+ ships PriorityQueue<TElement, TPriority>.

Benchmark: Measuring C# Collections Performance Yourself

Don't take Big-O tables on faith — measure. Here's a minimal BenchmarkDotNet comparison of lookups across 100,000 items:

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

[MemoryDiagnoser]
public class LookupBenchmarks
{
    private List<int> _list = null!;
    private HashSet<int> _set = null!;
    private Dictionary<int, int> _dict = null!;

    [GlobalSetup]
    public void Setup()
    {
        var data = Enumerable.Range(0, 100_000).ToArray();
        _list = data.ToList();
        _set  = data.ToHashSet();
        _dict = data.ToDictionary(x => x);
    }

    [Benchmark] public bool List_Contains()    => _list.Contains(99_999);
    [Benchmark] public bool HashSet_Contains() => _set.Contains(99_999);
    [Benchmark] public bool Dict_ContainsKey() => _dict.ContainsKey(99_999);
}

public class Program
{
    public static void Main() => BenchmarkRunner.Run<LookupBenchmarks>();
}

Typical results on a modern machine: List.Contains lands around 20–40 microseconds (it scans all 100,000 elements for a worst-case miss or last-element hit), while HashSet.Contains and Dictionary.ContainsKey land around 3–6 nanoseconds — roughly a 5,000–10,000x difference. The gap widens as the collection grows, because the hash-based collections simply don't care about size.

The flip side: for small collections (under ~20–50 elements), a List scan is often faster than a hash lookup, because scanning contiguous memory beats computing a hash and chasing bucket references. Big-O describes growth, not absolute speed.

Common Pitfalls (and How to Avoid Them)

1. Using List.Contains inside a loop

The single most common collections performance bug in C# codebases. Any O(n) search repeated n times is O(n²). Build a HashSet or Dictionary once before the loop, then query it inside.

2. Forgetting to set initial capacity

Growing a List or Dictionary from its default capacity to 1 million items triggers ~20 resize-and-copy operations and churns the garbage collector. If you know the size, say so: new List<T>(1_000_000).

3. Bad GetHashCode on dictionary keys

Hash collections are only O(1) if hashes distribute well. A custom key type that returns a constant (or doesn't override GetHashCode/Equals consistently) degrades a dictionary to a linked list — O(n) lookups. Use C# record types for keys; they generate correct equality and hashing for free.

4. Mutating keys after insertion

If an object's hash code changes while it's inside a HashSet or used as a Dictionary key, the collection can no longer find it — it's filed under the old hash. Use immutable keys, always.

5. Assuming Dictionary preserves insertion order

Current implementations often appear to enumerate in insertion order until a removal happens, and code that relies on it breaks unpredictably. If order matters, keep a separate List of keys or use SortedDictionary.

6. Modifying a collection while enumerating it

Removing items inside a foreach throws InvalidOperationException. Use List.RemoveAll(predicate), iterate a copy, or iterate backwards with a for loop.

Which C# Collection Should You Use? Quick Decision Guide

• Iterating, indexing, appending? → List<T> (the sensible default)
• Looking things up by a unique key? → Dictionary<TKey, TValue>
• Checking membership or enforcing uniqueness? → HashSet<T>
• Processing items in arrival order? → Queue<T> (or Stack<T> for last-in-first-out)
• Need sorted keys? → SortedDictionary<TKey, TValue> (O(log n) but ordered)
• Multiple threads? → ConcurrentDictionary, ConcurrentQueue, or System.Threading.Channels

Conclusion: Key Takeaways on C# Collections

Mastering C# collections performance comes down to matching the data structure to the dominant operation in your code. Here's what to remember:

• List<T> is the default: unbeatable iteration and indexed access, but O(n) searches.
• Dictionary<TKey, TValue> turns repeated key lookups from O(n) into O(1) — use TryGetValue, not ContainsKey plus the indexer.
• HashSet<T> is the answer to "have I seen this before?" — its Add return value checks and inserts in one step.
• Queue<T> gives O(1) removal from the front, which List fundamentally cannot.
• Pre-size collections when you know the count, keep keys immutable, and never call Contains on a list inside a loop.
• Big-O describes growth, not absolute speed — for tiny collections a plain list often wins. When in doubt, benchmark with BenchmarkDotNet.

The next time you type new List<, pause for two seconds and ask: what's the operation I'll run most against this data? That one habit will do more for your application's performance than most micro-optimizations ever will. Try swapping a hot-path list lookup for a HashSet or Dictionary in your own codebase this week — and measure the difference.

Tags: #C# collections #C# list vs dictionary #C# HashSet #C# Dictionary performance #C# Queue #collections in C# with examples

About csharp-coder.com
Your go-to resource for C#, .NET, and modern software development. Follow along for daily tutorials, tips, and real-world examples.