C# List vs Dictionary vs HashSet: Performance Guide

C# collections performance compared: List vs Dictionary vs HashSet vs Queue with Big O tables, benchmarks, and code. Learn which collection to use now.

Choosing the right C# collections is one of the highest-impact performance decisions you can make in .NET — and one of the most common interview questions for C# developers. Should you use a List<T>, a Dictionary<TKey, TValue>, a HashSet<T>, or a Queue<T>? Pick wrong, and a lookup that should take nanoseconds turns into a linear scan that melts your CPU at scale. In this C# collections performance guide, we compare all four with Big O complexity tables, runnable code examples, and real-world guidance on when to use each — so you never have to guess again.

Why C# Collections Performance Matters

Every collection in .NET is a trade-off between memory layout, lookup speed, insertion cost, and ordering guarantees. The difference between List<T>.Contains() and HashSet<T>.Contains() isn't a micro-optimization — it's the difference between O(n) and O(1). On a collection of 1 million items, that's the difference between roughly a million comparisons and a single hash lookup.

Here's the quick-reference table you came for:

Big O Complexity Cheat Sheet

• List<T> — Add: O(1) amortized · Lookup by index: O(1) · Search (Contains): O(n) · Remove: O(n)
• Dictionary<TKey, TValue> — Add: O(1) · Lookup by key: O(1) · Contains key: O(1) · Remove: O(1)
• HashSet<T> — Add: O(1) · Contains: O(1) · Remove: O(1) · Set operations: O(n)
• Queue<T> — Enqueue: O(1) amortized · Dequeue: O(1) · Peek: O(1) · Search: O(n)

The WHY behind these numbers comes down to how each collection stores data in memory. Let's break each one down.

List<T>: The Default Workhorse

A List<T> is a dynamic array. Under the hood it's a contiguous block of memory, which makes it extremely cache-friendly. Iterating a list is the fastest iteration in .NET because the CPU prefetcher loves sequential memory access.

var orders = new List<Order>();
orders.Add(new Order { Id = 1, Total = 99.50m });
orders.Add(new Order { Id = 2, Total = 45.00m });

// O(1) — direct index access, blazing fast
Order first = orders[0];

// O(n) — walks every element until it finds a match. Danger zone!
bool exists = orders.Any(o => o.Id == 2);

The hidden cost: resizing

When a list's internal array fills up, .NET allocates a new array double the size and copies everything over. If you know the size upfront, always set the capacity — it eliminates every intermediate allocation and copy:

// Bad: grows 4 → 8 → 16 → ... → 131072, copying each time
var slow = new List<int>();

// Good: one allocation, zero copies
var fast = new List<int>(capacity: 100_000);
for (int i = 0; i < 100_000; i++)
    fast.Add(i);

Use List<T> when: you need ordered data, index access, duplicates are allowed, and you mostly iterate rather than search.

Avoid List<T> when: you repeatedly call Contains, Find, or Any on large data — that's an O(n) scan every single time.

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

A Dictionary is a hash table. When you add a key, .NET calls GetHashCode() on it, uses the hash to compute a bucket index, and stores the entry there. Lookup reverses the process: hash the key, jump straight to the bucket. No scanning — that's why it's O(1).

var productsBySku = new Dictionary<string, Product>
{
    ["SKU-1001"] = new Product("Mechanical Keyboard", 89.99m),
    ["SKU-1002"] = new Product("USB-C Hub", 39.99m)
};

// O(1) lookup — one hash computation, regardless of dictionary size
if (productsBySku.TryGetValue("SKU-1001", out Product? product))
{
    Console.WriteLine($"{product.Name}: {product.Price:C}");
}

Best practice: TryGetValue over ContainsKey + indexer

A common pitfall is checking and then fetching — that hashes the key twice:

// Pitfall: two hash lookups
if (productsBySku.ContainsKey("SKU-1001"))
{
    var p = productsBySku["SKU-1001"]; // second lookup!
}

// Best practice: one lookup
if (productsBySku.TryGetValue("SKU-1001", out var p2)) { /* use p2 */ }

The classic performance win: replacing nested loops

The single most common C# performance bug in real codebases is joining two lists with nested loops — O(n×m). A dictionary turns it into O(n+m):

// O(n × m): 10,000 customers × 50,000 orders = 500 million comparisons
foreach (var customer in customers)
    customer.Orders = orders.Where(o => o.CustomerId == customer.Id).ToList();

// O(n + m): build the lookup once, then O(1) per customer
var ordersByCustomer = orders
    .GroupBy(o => o.CustomerId)
    .ToDictionary(g => g.Key, g => g.ToList());

foreach (var customer in customers)
    customer.Orders = ordersByCustomer.GetValueOrDefault(customer.Id, new List<Order>());

Use Dictionary when: you look up values by a unique key. Avoid it when: you need ordering (use SortedDictionary) or you only iterate (a List iterates faster and uses less memory).

HashSet<T>: Fast Membership Tests and Deduplication

A HashSet<T> is essentially a dictionary with only keys — it stores unique values and answers "is this in the set?" in O(1). If you've ever written list.Contains(x) inside a loop, a HashSet is almost certainly what you wanted.

var bannedIps = new HashSet<string> { "10.0.0.5", "192.168.1.99" };

// O(1) — same speed whether the set has 10 entries or 10 million
bool blocked = bannedIps.Contains("10.0.0.5");

// Add returns false if the item already exists — free duplicate detection
bool added = bannedIps.Add("10.0.0.5"); // false, already present

Set operations: the underrated superpower

var currentUsers  = new HashSet<int> { 1, 2, 3, 4, 5 };
var premiumUsers  = new HashSet<int> { 3, 4, 5, 6, 7 };

currentUsers.IntersectWith(premiumUsers); // { 3, 4, 5 } — active premium users

Real numbers: HashSet vs List Contains

A simple BenchmarkDotNet run checking membership of 1,000 items against a 100,000-element collection tells the story: List.Contains takes on the order of tens of milliseconds, while HashSet.Contains finishes in microseconds — a 1,000×+ difference that grows linearly with collection size.

Pitfall: HashSet gives you no ordering and no index access, and custom types must implement GetHashCode() and Equals() correctly (or you'll get duplicates that "look" equal). C# record types give you both for free — prefer them for set elements and dictionary keys.

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

A Queue<T> is a circular buffer that processes items in arrival order (FIFO). Both Enqueue and Dequeue are O(1) — compare that to list.RemoveAt(0), which is O(n) because every remaining element shifts left.

var jobs = new Queue<string>();
jobs.Enqueue("resize-image-01.png");
jobs.Enqueue("resize-image-02.png");
jobs.Enqueue("send-email-batch");

while (jobs.Count > 0)
{
    string job = jobs.Dequeue(); // O(1), preserves order
    Console.WriteLine($"Processing: {job}");
}

Use Queue when: order of processing matters — job pipelines, breadth-first search, message buffering, rate limiting. For producer/consumer scenarios across threads, reach for ConcurrentQueue<T> or System.Threading.Channels instead — a plain Queue<T> is not thread-safe.

C# Collections Performance: Which One Should You Use?

Ask these questions in order:

• Do you look items up by a key? → Dictionary<TKey, TValue>
• Do you only need "does it exist?" and uniqueness? → HashSet<T>
• Do you process items in arrival order? → Queue<T> (or Stack<T> for LIFO)
• Everything else — ordered data, iteration, index access? → List<T>

Common pitfalls recap

• Calling Contains/Any on a List inside a loop — convert to a HashSet or Dictionary first.
• Forgetting to set initial capacity when the size is known — causes repeated array resizing and Gen0 GC pressure.
• Using list.RemoveAt(0) as a queue — O(n) per removal; use Queue<T>.
• Using mutable classes as dictionary keys without overriding GetHashCode — items silently get "lost" if the hash changes after insertion.
• Exposing List<T> in public APIs — return IReadOnlyList<T> or IEnumerable<T> to protect invariants.

Conclusion: Key Takeaways on C# Collections

Mastering C# collections performance boils down to matching the data structure to the access pattern. Use List<T> for ordered, iterated data; Dictionary<TKey, TValue> for keyed O(1) lookups; HashSet<T> for uniqueness and membership checks; and Queue<T> for FIFO processing. The Big O table is your compass, but remember the hidden costs too: resizing, hash quality, and cache locality all show up at scale. When in doubt, measure with BenchmarkDotNet — but nine times out of ten, replacing an O(n) list scan with an O(1) hash lookup is the single biggest performance win available in your C# code.

Tags: #C# List vs Dictionary #C# HashSet vs List performance #C# Dictionary performance #C# Queue example #Big O complexity C# #best collection C#

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.