Choosing the Right C# Collection

Why collection choice matters more than it looks

Picking the wrong collection type is one of the most common sources of subtle .NET performance bugs — List.Contains when you should use HashSet, loading a full dictionary value when TryGetValue does one lookup, or calling Count() on an IEnumerable<T> that executes a database query. This guide gives you a framework for choosing correctly.

The collection hierarchy

IEnumerable<T>           — iterate only (foreach)
  ICollection<T>         — + Count, Add, Remove, Contains
    IList<T>             — + indexer [], Insert, RemoveAt

  IReadOnlyCollection<T> — Count + enumeration (no mutation)
    IReadOnlyList<T>     — + indexer []

Accept the most general type your method needs; return the most specific the caller needs.

// Accept IEnumerable<T> when you only iterate:
int Sum(IEnumerable<int> items) => items.Sum();
Sum(new[] { 1, 2, 3 });           // array — ok
Sum(new List<int> { 1, 2 });      // list — ok
Sum(Enumerable.Range(1, 100));     // lazy — ok

// Return IReadOnlyList<T> when the caller needs indexed access but not mutation:
public IReadOnlyList<Order> GetOrders() => _orders.AsReadOnly();

List<T> vs Array (T)

// Array — fixed size at creation; fastest indexed access:
int[] arr = new int[5];
arr[0] = 1;
// arr.Add(6); — doesn't exist

// List<T> — dynamic; backed by an internal array that resizes:
var list = new List<int>(capacity: 5); // pre-size to avoid early resizes
list.Add(1); list.Add(2); // grows when capacity is exceeded

// Both support zero-copy Span<T> slicing:
Span<int> spanArr  = arr.AsSpan();
Span<int> spanList = list.AsSpan();       // .NET 5+

// API difference:
arr.Length;    // fixed count
list.Count;    // current element count
list.Capacity; // internal array size (>= Count)

When to use array: size is known up-front, no need to add/remove, performance critical (marginally faster indexing). When to use List<T>: size changes, needs Add/Remove. When to return from a public method: return IReadOnlyList<T> to expose indexed access without allowing mutation of your internal list.

Dictionary<TKey, TValue> — how it works and what makes a good key

Dictionary<TKey, TValue> is a hash table:

1. Call key.GetHashCode() → determines bucket
2. Walk bucket entries, call key.Equals(entry.Key) for each → find exact match

Average O(1) lookup, insert, remove. Worst case O(n) if all keys hash to the same bucket.

// Safe access — single lookup:
var dict = new Dictionary<string, int> { ["a"] = 1, ["b"] = 2 };

// Two lookups — ContainsKey then indexer:
if (dict.ContainsKey("a")) { int v = dict["a"]; }

// One lookup:
if (dict.TryGetValue("a", out int val)) { /* use val */ }

// Default if missing:
int count = dict.GetValueOrDefault("missing", 0);

// In-place increment (CollectionsMarshal — zero allocation, .NET 6+):
ref int hits = ref CollectionsMarshal.GetValueRefOrAddDefault(dict, "hits", out _);
hits++;

// Custom comparer — case-insensitive keys:
var ci = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
ci["Hello"] = 1;
Console.WriteLine(ci["hello"]); // 1

// Pre-size to avoid rehashing:
var big = new Dictionary<string, int>(capacity: 10_000);

Key design rules:

• Keys must have stable GetHashCode values — never mutate an object while it is a dictionary key.
• For custom types, override both GetHashCode and Equals, or use records (which do this automatically via value equality).
• Never use mutable reference types with default GetHashCode (pointer-based) as keys.

HashSet<T> for fast membership

var banned = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "admin", "root", "superuser"
};

// O(1) lookup — vs O(n) for List<T>.Contains:
bool isBanned = banned.Contains(username); // fast regardless of set size

// Uniqueness — duplicates silently ignored:
banned.Add("admin"); // returns false; set unchanged

// Set operations:
var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };

a.IntersectWith(b);  // a = { 3, 4 } — in-place
a.UnionWith(b);      // a = { 3, 4, 5, 6 }
a.ExceptWith(b);     // a = {} (b is superset here)

// Remove duplicates from a list:
var deduped = new HashSet<string>(list).ToList();

// Sorted variant:
var sorted = new SortedSet<int> { 5, 1, 3, 2 }; // always ordered: 1, 2, 3, 5

Rule: Use HashSet<T> whenever you're checking "is X in this set?" at scale. List<T>.Contains is O(n); HashSet<T>.Contains is O(1).

ConcurrentDictionary for thread-safe caching

// Thread-safe cache:
var cache = new ConcurrentDictionary<string, UserProfile>();

// GetOrAdd — returns existing value or adds new one atomically:
var profile = cache.GetOrAdd(userId, id => LoadFromDb(id));
// WARNING: the factory may run multiple times under contention
// Use Lazy<T> to ensure single initialization:
var lazyCache = new ConcurrentDictionary<string, Lazy<UserProfile>>();
var lazy = lazyCache.GetOrAdd(userId, id => new Lazy<UserProfile>(() => LoadFromDb(id)));
UserProfile p = lazy.Value;

// AddOrUpdate — atomic add-or-modify:
cache2.AddOrUpdate("hits", 1, (key, old) => old + 1);

// TryGetValue, TryAdd, TryRemove — all atomic:
if (cache.TryGetValue(userId, out var existing))
    Console.WriteLine(existing.Name);

// foreach is safe — enumerates a snapshot (may be slightly stale under concurrent writes)
foreach (var (key, value) in cache)
    Console.WriteLine(key);

Avoid wrapping Dictionary<K,V> in lock — ConcurrentDictionary is more efficient for read-heavy workloads using fine-grained locking per bucket.

IReadOnlyList vs ImmutableList

// IReadOnlyList<T> — view over a mutable list; caller can't add/remove
var internal = new List<int> { 1, 2, 3 };
IReadOnlyList<int> view = internal;
// view.Add(4); — compile error
internal.Add(4);
Console.WriteLine(view.Count); // 4 — view reflects the change!

// ImmutableList<T> — truly unchangeable; modifications return a new list
var immutable = ImmutableList.Create(1, 2, 3);
var updated = immutable.Add(4);   // new list
Console.WriteLine(immutable.Count); // 3 — original unchanged
Console.WriteLine(updated.Count);   // 4

// ImmutableArray<T> — better performance than ImmutableList for indexed access:
var arr = ImmutableArray.Create(1, 2, 3);
var arr2 = arr.Add(4); // arr still [1, 2, 3]

IReadOnlyList<T> prevents the caller from mutating but the producer can still change the underlying list. ImmutableList<T> (from System.Collections.Immutable) is truly immutable — safe to share across threads without locking.

Span<T> and Memory<T> — zero-allocation slicing

Span<T> is a stack-only struct that represents a contiguous memory region without copying it:

int[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };

// Zero-copy slice:
Span<int> slice = array.AsSpan(2, 4); // [3, 4, 5, 6]
slice[0] = 99;                          // modifies the ORIGINAL array!

// Stack allocation — no heap involved:
Span<byte> buf = stackalloc byte[1024];
buf.Fill(0);

// String parsing without allocating substrings:
ReadOnlySpan<char> csv = "Alice,30,London".AsSpan();
int first  = csv.IndexOf(',');
ReadOnlySpan<char> name = csv[..first]; // "Alice" — zero allocation

// Memory<T> — heap-allocated Span for async code:
async Task ProcessAsync(Memory<byte> buffer)
{
    await stream.ReadAsync(buffer); // Memory<T> crosses await boundaries
    ReadOnlySpan<byte> span = buffer.Span; // access as Span in sync code
}

Span<T> cannot cross await boundaries (it's a stack ref type). Use Memory<T> when you need to store the reference or pass it across async calls.

Queue, Stack, and sorted collections

// Queue<T> — FIFO; O(1) Enqueue/Dequeue
var queue = new Queue<Task>();
queue.Enqueue(task1);
var next = queue.Dequeue();

// Stack<T> — LIFO; O(1) Push/Pop
var history = new Stack<Command>();
history.Push(cmd);
var undone = history.Pop();

// SortedDictionary<K,V> — red-black tree; O(log n) all ops; iteration in key order
var sorted = new SortedDictionary<int, string>();
sorted[3] = "c"; sorted[1] = "a"; sorted[2] = "b";
foreach (var kv in sorted) Console.Write(kv.Key); // 1 2 3

// SortedList<K,V> — parallel arrays; O(log n) lookup, O(n) insert
// Supports index-based access: sl.Keys[0], sl.Values[0]
// More memory-efficient than SortedDictionary for read-heavy, loaded-once data

Key performance tips

// 1. Pre-size when count is known:
var list = new List<Order>(capacity: orders.Length);
var dict = new Dictionary<string, int>(capacity: 1000);

// 2. TryGetValue over ContainsKey + indexer:
if (dict.TryGetValue(key, out int v)) Use(v); // one lookup

// 3. CollectionsMarshal for in-place dict value update (.NET 6+):
ref int counter = ref CollectionsMarshal.GetValueRefOrAddDefault(dict, "key", out _);
counter++;

// 4. Span over LINQ for hot-path buffer ops:
var data = largeArray.AsSpan(offset, length);
foreach (var n in data) Process(n); // no enumerator allocation

// 5. AsReadOnly() to expose List<T> safely:
public IReadOnlyList<Order> Orders => _orders.AsReadOnly();

Recap

Start with List<T> for ordered mutable sequences; use T[] when the size is fixed. Use Dictionary<TKey, TValue> for O(1) key-based lookup — always call TryGetValue instead of ContainsKey + indexer. Use HashSet<T> for membership tests and uniqueness. Use ConcurrentDictionary for thread-safe caches. Return IReadOnlyList<T> from public APIs to prevent mutation of internal state. Use ImmutableList<T> or ImmutableArray<T> when you need a truly immutable, shareable collection. Use Span<T> and Memory<T> to slice buffers without allocation — Span<T> in synchronous hot paths, Memory<T> across async calls. Pre-size collections when the count is known. In thread-safe code, use ConcurrentDictionary rather than a lock-wrapped Dictionary.