C# List vs Dictionary vs HashSet: Performance Guide

Learn C# collections performance: List vs Dictionary vs HashSet vs Queue with Big-O costs, benchmarks, and code examples. Pick the right collection today.

Choosing the right C# collections is one of the highest-leverage performance decisions you can make in .NET. A List<T> that works fine with 100 items can quietly turn into a bottleneck at 100,000 items, while swapping it for a HashSet<T> or Dictionary<TKey, TValue> can cut lookup time from milliseconds to nanoseconds. This guide compares List vs Dictionary vs HashSet vs Queue in C#, explains the Big-O cost of every common operation, shows runnable code, and gives you a decision checklist you can apply to real projects.

Why C# Collections Performance Matters

All four collections live in System.Collections.Generic and all of them implement IEnumerable<T>, so from a LINQ perspective they look interchangeable. They are not. Each one is backed by a different data structure, and that structure dictates how fast add, lookup, remove, and enumerate are:

• List<T> – a growable array. Fast indexed access, slow searching.
• Dictionary<TKey, TValue> – a hash table of key/value pairs. Near-constant-time lookup by key.
• HashSet<T> – a hash table of unique values. Near-constant-time membership tests.
• Queue<T> – a circular array. Constant-time first-in, first-out (FIFO) operations.

Understanding the underlying structure lets you predict performance before you profile, which is exactly what senior engineers do in code review.

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

Operation	List<T>	Dictionary<K,V>	HashSet<T>	Queue<T>
Add to end / Enqueue	O(1) amortized	O(1) amortized	O(1) amortized	O(1) amortized
Insert at index 0	O(n)	n/a	n/a	n/a
Access by index	O(1)	n/a	n/a	n/a
Lookup by key / Contains	O(n)	O(1)	O(1)	O(n)
Remove specific item	O(n)	O(1)	O(1)	n/a
Dequeue / RemoveAt(0)	O(n)	n/a	n/a	O(1)
Preserves insertion order	Yes	Not guaranteed	Not guaranteed	Yes (FIFO)

The single most important row is Lookup / Contains. List<T>.Contains walks every element; HashSet<T>.Contains hashes the value and jumps straight to its bucket. At 1 million items that is the difference between roughly 1 million comparisons and one.

List<T>: The Default, But Not Always the Right One

List<T> wraps a T[] array. When the array fills up, .NET allocates a new array twice the size and copies everything over. That is why Add is O(1) amortized: most adds are cheap, and the occasional resize is spread across them.

using System;
using System.Collections.Generic;

var orders = new List<int>(capacity: 1_000_000); // pre-size to avoid resizes

for (int i = 0; i < 1_000_000; i++)
{
    orders.Add(i);
}

// O(1): indexed access is what List is best at
int fifth = orders[4];

// O(n): this scans the whole list on a miss
bool hasOrder = orders.Contains(999_999);

Console.WriteLine($"Fifth: {fifth}, contains: {hasOrder}");

Use List<T> when: you need ordered data, index-based access, or you mostly iterate rather than search. Avoid it when: you call Contains, IndexOf, or Remove(item) inside a loop — that turns an O(n) algorithm into O(n²).

Pitfall: Insert(0, item) and RemoveAt(0)

Both shift every remaining element one slot. Doing this in a loop over a large list is a classic hidden O(n²). If you need to remove from the front, that is a signal you want a Queue<T>.

Dictionary<TKey, TValue>: Fast Lookup by Key

A Dictionary computes GetHashCode() on the key, uses it to pick a bucket, then compares with Equals() to resolve collisions. With a good hash function, lookup, insert, and remove are all O(1) on average. This is the workhorse for the C# list vs dictionary question: if you ever look items up by an ID, use a Dictionary.

using System;
using System.Collections.Generic;

public record Customer(int Id, string Name);

var customersById = new Dictionary<int, Customer>();

customersById[1] = new Customer(1, "Ada");
customersById[2] = new Customer(2, "Linus");

// O(1) lookup — prefer TryGetValue over ContainsKey + indexer (avoids double hashing)
if (customersById.TryGetValue(2, out var customer))
{
    Console.WriteLine($"Found {customer.Name}");
}

// TryAdd avoids the exception thrown by Add on duplicate keys
bool added = customersById.TryAdd(1, new Customer(1, "Duplicate"));
Console.WriteLine($"Added duplicate? {added}"); // False

Best practices for Dictionary performance

• Use TryGetValue instead of ContainsKey followed by dict[key]. The second pattern hashes the key twice.
• Pre-size with a capacity when you know the count. Rehashing on growth is expensive.
• Keys must have a stable, well-distributed hash. Records and primitive types are fine. If you write a custom class, override both Equals and GetHashCode — or use a record.
• Use StringComparer.OrdinalIgnoreCase for case-insensitive string keys instead of calling ToLower() everywhere, which allocates a new string per lookup.
• Never mutate a key after inserting it. The stored hash goes stale and the entry becomes unreachable.

HashSet<T>: Fast Membership Tests and Uniqueness

A HashSet<T> is essentially a Dictionary with keys but no values. It answers one question extremely fast: "Is this item in the set?" It also enforces uniqueness for free — Add returns false instead of inserting a duplicate.

using System;
using System.Collections.Generic;
using System.Diagnostics;

var list = new List<int>();
var set  = new HashSet<int>();

for (int i = 0; i < 100_000; i++)
{
    list.Add(i);
    set.Add(i);
}

var sw = Stopwatch.StartNew();
int hits = 0;
for (int i = 0; i < 10_000; i++)
{
    if (list.Contains(99_999 - i)) hits++; // O(n) each
}
sw.Stop();
Console.WriteLine($"List.Contains x10k:    {sw.ElapsedMilliseconds} ms");

sw.Restart();
hits = 0;
for (int i = 0; i < 10_000; i++)
{
    if (set.Contains(99_999 - i)) hits++; // O(1) each
}
sw.Stop();
Console.WriteLine($"HashSet.Contains x10k: {sw.ElapsedMilliseconds} ms");

On a typical machine the List version takes hundreds of milliseconds while the HashSet version finishes in well under one millisecond. That is the list vs HashSet C# difference in one screen of code. (For rigorous numbers, use BenchmarkDotNet rather than Stopwatch; the ratio holds either way.)

Set operations built in

HashSet also ships with UnionWith, IntersectWith, ExceptWith, and IsSubsetOf. They are dramatically faster than the LINQ equivalents on lists because both sides are hashed.

var activeUsers  = new HashSet<string> { "ada", "linus", "grace" };
var adminUsers   = new HashSet<string> { "grace", "dennis" };

var activeAdmins = new HashSet<string>(activeUsers);
activeAdmins.IntersectWith(adminUsers); // { "grace" }

Use HashSet<T> when: you need "have I seen this before?" checks, de-duplication, or set algebra. Avoid it when: you need ordering or indexed access — a HashSet has neither.

Queue<T>: First-In, First-Out Without the O(n) Penalty

Queue<T> is backed by a circular buffer with a head and tail index. Enqueue writes at the tail; Dequeue reads at the head and advances it. No element shifting, so both are O(1). It is the correct tool for work items, breadth-first search, message buffering, and rate-limiting windows.

using System;
using System.Collections.Generic;

var jobs = new Queue<string>();
jobs.Enqueue("resize-image");
jobs.Enqueue("send-email");
jobs.Enqueue("generate-pdf");

while (jobs.TryDequeue(out var job))   // TryDequeue avoids an exception on empty
{
    Console.WriteLine($"Processing {job} ({jobs.Count} remaining)");
}

// Peek looks at the next item without removing it
var pending = new Queue<int>(new[] { 1, 2, 3 });
Console.WriteLine(pending.Peek()); // 1

If you were previously doing list.RemoveAt(0) to simulate a queue, switching to Queue<T> is a pure win. For multi-threaded producers and consumers, use ConcurrentQueue<T> or System.Threading.Channels instead — the plain Queue<T> is not thread-safe.

Real-World Example: Fixing an O(n²) Bug

Here is a pattern that appears in countless codebases — finding which orders belong to a set of customer IDs:

// ❌ Slow: List.Contains inside a loop = O(orders × customerIds)
List<int> customerIds = LoadCustomerIds();       // 50,000 items
List<Order> orders    = LoadOrders();            // 500,000 items

var matches = orders.Where(o => customerIds.Contains(o.CustomerId)).ToList();

// ✅ Fast: one O(n) pass to build the set, then O(1) per lookup
var idSet = new HashSet<int>(customerIds);
var fastMatches = orders.Where(o => idSet.Contains(o.CustomerId)).ToList();

The first version performs up to 25 billion comparisons. The second performs about 550,000 hash operations. Same result, same LINQ shape, roughly four orders of magnitude faster. Building a HashSet or Dictionary once and then querying it in a loop is the most common collections optimization in C#.

Memory and Enumeration Trade-offs

Hash-based collections are not free. Each Dictionary entry stores the hash code, a bucket pointer, the key, and the value, so it uses roughly 2–3× the memory of a List of the same items. Enumeration over a List is also faster and more cache-friendly because it is a contiguous array. Practical rules:

• Fewer than ~20 items and mostly iterating? List<T> is usually fastest even for Contains, because hashing overhead outweighs the linear scan.
• Need order and fast lookup? Keep a List for order plus a HashSet or Dictionary as an index, or use SortedDictionary/SortedSet if sorted-order iteration is required (O(log n) operations).
• Exposing collections from a public API? Return IReadOnlyList<T>, IReadOnlyDictionary<K,V>, or IReadOnlySet<T> so callers cannot mutate your internal state.

Decision Checklist: Which C# Collection Should I Use?

• I access items by position or need to keep insertion order → List<T>
• I look items up by a key (ID, name, code) → Dictionary<TKey, TValue>
• I only need to know whether an item exists, or I need unique values → HashSet<T>
• I process items in the order they arrived → Queue<T>
• I process the most recent item first → Stack<T>
• I need the smallest/highest-priority item first → PriorityQueue<TElement, TPriority> (.NET 6+)
• Multiple threads read and write → ConcurrentDictionary, ConcurrentQueue, or Channel<T>

Common Pitfalls to Avoid

• Calling Contains on a List inside a loop. Build a HashSet first.
• Modifying a collection while enumerating it. Throws InvalidOperationException. Use RemoveAll on lists, or collect keys to delete and remove afterwards on dictionaries. (.NET Core 3.0+ allows Dictionary.Remove during enumeration, but it is still clearer to avoid it.)
• Using a mutable class as a Dictionary key without overriding GetHashCode. You get reference equality, which is rarely what you intended.
• Relying on Dictionary or HashSet ordering. It happens to look like insertion order for small, add-only sets, but it is not guaranteed and breaks after removals.
• Using LINQ .Count() instead of the .Count property. The property is O(1); the method may enumerate.
• Ignoring capacity. If you know you'll add 1 million items, say so in the constructor and skip ~20 resize-and-copy cycles.

Conclusion: Choosing C# Collections for Performance

Picking the right C# collections is less about memorizing benchmarks and more about matching the data structure to the operation you perform most. List<T> wins for ordered, index-based, iteration-heavy work. Dictionary<TKey, TValue> wins the moment you look things up by key. HashSet<T> wins for existence checks and uniqueness. Queue<T> wins for FIFO processing. Key takeaways:

• List.Contains is O(n); HashSet.Contains and Dictionary.TryGetValue are O(1). This one fact fixes most collection performance bugs.
• Never remove from the front of a List in a loop — use a Queue.
• Pre-size collections when you know the count, and prefer TryGetValue, TryAdd, and TryDequeue over exception-throwing alternatives.
• Hash-based collections cost more memory and lose ordering; for tiny collections, a List is often fastest anyway.
• Measure with BenchmarkDotNet before and after — the numbers will confirm the Big-O story.

Apply the decision checklist above the next time you type new List< by reflex, and you'll write C# that scales from prototype to production without a rewrite.

Tags: #c# list vs dictionary #c# hashset #c# dictionary performance #c# queue #list vs hashset c# #c# collections performance

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.