Collections Internals Interview Questions for .NET Developers

Q1 How does Dictionary<TKey, TValue> work internally? Walk through what happens on Add.#

Short answer: A Dictionary<TKey, TValue> is a bucket array of integers pointing into a parallel array of entries; each entry stores its computed hash code, the key, the value, and an index to the next entry in its bucket's collision chain, so lookups are an O(1) average-case hash-and-walk rather than a scan.

Internally there are two arrays: _buckets, an int[] sized to a prime number, and _entries, an array of structs each holding the entry's stored hash code, a next index for chaining, the key and the value. A bucket slot holds a 1-based index into _entries (0 means empty), so the bucket array itself never stores keys or values directly — only where to start looking. On Add, the dictionary computes the key's hash code (via the configured IEqualityComparer<TKey> or the key's own GetHashCode), reduces it to a bucket index with a modulo against the bucket array's length, and walks the chain starting at that bucket comparing stored hash codes first (a cheap integer comparison) and only calling Equals on a hash match, to detect duplicates. If the key is new, the entry is written into the next free slot in _entries — reusing a slot from an internal free list if one exists from a prior removal, or appending if not — and the bucket is updated to point to the new entry, with the new entry's next set to whatever the bucket previously pointed to, so chains grow from the head. The bucket array is deliberately sized to prime numbers (via an internal GetPrime helper) rather than a power of two, because prime moduli distribute hash codes across buckets more evenly for common hash functions, reducing clustering. When the entries array fills up, the dictionary resizes to the next prime at roughly double the size and rehashes every live entry into the new, larger bucket array — an O(n) operation, which is why growth is doubling rather than linear, to keep the amortized cost of many Add calls at O(1).

var cache = new Dictionary<string, decimal>(capacity: 10_000, comparer: StringComparer.Ordinal);
cache["order:4471"] = 129.99m; // hash -> bucket -> walk chain -> not found -> insert

What interviewers look for: the separate-chaining model (bucket array of indices into an entries array, not buckets containing linked list nodes on the heap), and the fact that resizing rehashes everything, which is why presizing matters for large, known-size dictionaries.

• Common mistakes: describing Dictionary<TKey, TValue> as using open addressing or as directly storing linked lists of heap-allocated nodes per bucket, rather than an index-based chain inside a single contiguous entries array.
• Follow-up questions: why store the hash code in the entry instead of recomputing it during resize? What happens to Count versus Capacity after a large number of Remove calls?

Q2 Why does List<T> sometimes reallocate on every single Add, and how do you avoid it in a hot path?#

Short answer: A List<T> wraps a plain array plus a logical size; a brand-new list has zero capacity, the first Add grows it to a small default, and every subsequent Add that exceeds the current array's length doubles the capacity, copying every existing element into the new array — so a tight loop of Add calls on a list with unknown final size pays for O(log n) full-array copies, not one.

An empty List<T> starts by referencing a shared, zero-length array, so constructing one that's never populated allocates nothing. The first Add allocates an array of capacity 4. From there, whenever Add needs more room than the backing array has, List<T> allocates a new array of double the current capacity and copies every existing element across before appending the new one — an O(n) operation. Across a full run from empty to n elements, this happens O(log₂ n) times, and because each copy is roughly twice the size of the last, the total copying work sums to O(n), which is why Add is described as amortized O(1): most calls are O(1), but the calls that trigger a grow are O(n), and a latency-sensitive hot path that can't tolerate an occasional O(n) Add needs to avoid triggering growth in the critical section at all.

The fix, when the final or approximate size is knowable ahead of time, is presizing:

// Without presizing: several reallocate-and-copy cycles as the list grows past 4, 8, 16, 32...
var results = new List<OrderLine>();
foreach (var row in rows) results.Add(Map(row));

// With presizing: one allocation, no mid-loop copies.
var results = new List<OrderLine>(rows.Count);
foreach (var row in rows) results.Add(Map(row));

List<T>.EnsureCapacity(int) does the same thing after the fact if the count becomes known partway through. The doubling strategy also means a list that grew large and then shrank still holds the peak capacity's memory until you explicitly call TrimExcess(), which is worth knowing when a short-lived spike in list size leaves a long-lived object holding onto memory it no longer needs.

What interviewers look for: the empty-then-4-then-doubling growth curve specifically, the amortized O(1) versus worst-case O(n) distinction for a single Add, and unprompted mention of presizing as the fix rather than "use an array instead," which just moves the sizing problem to the caller.

• Follow-up questions: why does capacity double instead of growing by a fixed increment? What's the memory cost of guessing an initial capacity that's much too large?

Q3 How is HashSet<T> different from Dictionary<TKey, TValue> internally, given that both need hashing?#

Short answer: They aren't very different at all — HashSet<T> uses the same bucket-array-plus-entries layout as Dictionary<TKey, TValue>, with the entry storing the element and its hash code but no separate value payload, since a set only needs to know whether an item is present, not what it maps to.

This alignment isn't a coincidence; the two types share essentially identical internal mechanics for insertion, lookup and resizing — prime-sized bucket array, chained entries with a stored hash code and a next index, and a free list for reused slots after removal. The practical difference is entirely at the API surface: HashSet<T> exposes set algebra — UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith, and IsSubsetOf/IsSupersetOf/Overlaps — and these operations are implemented to work directly against the internal bucket structure of both operands where possible, which is significantly faster than the naive approach of iterating one set and doing a lookup per item against the other for every operation. So the choice between the two is really a choice about the shape of your data: if you need "is this key present, and if so what's associated with it," use Dictionary<TKey, TValue>; if you only need "is this item present" or need efficient set algebra, use HashSet<T> — reaching for a Dictionary<TKey, bool> as a substitute for a set is a common, unnecessary habit that wastes memory on an unused value slot per entry.

What interviewers look for: knowing that the shared internal design is deliberate and relatively recent history in the runtime, and that the real decision driver is the API shape (key-value association vs. set membership and set algebra), not a performance difference between the two.

• Common mistakes: assuming HashSet<T> must be slower or more memory-heavy than Dictionary<TKey, TValue> because it "does less," when in practice its entries are smaller precisely because there's no value field.
• Follow-up questions: how would you implement SymmetricExceptWith efficiently without allocating a new set for every pairwise comparison? When would a FrozenSet<T> beat a plain HashSet<T>?

Q4 When would you reach for SortedDictionary<TKey,TValue>, SortedList<TKey,TValue> or SortedSet<T> instead of a hash-based collection?#

Short answer: Reach for a sorted collection when you need ordered enumeration, range queries, or "find the next key greater than X" — none of which a hash-based collection can do without a full sort first — and choose between SortedDictionary/SortedSet and SortedList based on how often you mutate the collection after it's built: tree-based types for frequent inserts and removes, SortedList for build-once, read-many, or index-based access.

SortedDictionary<TKey, TValue> and SortedSet<T> are both backed by a self-balancing binary search tree — specifically a red-black tree — internally; in fact, SortedDictionary<TKey, TValue> is implemented as a thin wrapper around the same tree engine SortedSet<T> uses, storing KeyValuePair<TKey, TValue> nodes ordered by key via the tree's comparer. That gives O(log n) Add, Remove and lookup with the tree staying balanced after every mutation, and in-order traversal falls out of the tree structure for free. SortedList<TKey, TValue>, in contrast, is backed by two parallel arrays — one for keys, one for values — kept sorted by key at all times. Lookup by key uses binary search, which is O(log n) and has excellent cache locality since it's a flat array scan, not pointer chasing through tree nodes; but Insert and Remove are O(n), because keeping the arrays sorted and contiguous means shifting every element after the insertion or removal point. SortedList also supports O(1) access by index, which the tree-based types don't offer directly.

The practical rule: if the collection is built once (or grows rarely) and then read or indexed heavily, SortedList wins on memory footprint and cache locality; if inserts and removes happen continuously after the initial population — an order book, a priority queue built from scratch — the tree-based types avoid the O(n) shifting cost.

What interviewers look for: knowing the concrete backing structures, not just "one is a tree and one is a list," and the ability to state the insert/remove asymmetry between them as the actual decision criterion rather than a vague "SortedList is for small collections" rule of thumb.

• Follow-up questions: why is SortedList described as more memory-efficient than SortedDictionary for the same data? What would you use instead of any of these three for a classic priority queue?

Q5 How does ConcurrentDictionary<TKey, TValue> achieve thread safety without a single global lock?#

Short answer: It uses lock striping — an array of locks, each owning a slice of the bucket array — so writers only contend when they happen to hash into the same slice, and reads are lock-free entirely, reading through volatile fields so a reader never blocks behind a writer and never sees a torn entry.

Internally, ConcurrentDictionary<TKey, TValue> holds a Tables object bundling the bucket array, an object[] of locks, and a per-lock live-entry counter. A write operation hashes the key to find its bucket, derives which lock in the striped lock array owns that bucket, and only acquires that one lock — by default, the number of locks is sized to the processor count, so on an 8-core machine, roughly one eighth of write traffic contends with any other given write, not all of it. Each bucket is a singly linked list of nodes rather than the index-into-array layout Dictionary<TKey, TValue> uses, because nodes can be safely published to readers via a volatile reference without the reader needing to take any lock at all: a reader walks the chain following volatile-read node references, and because nodes are only ever appended or fully replaced, never mutated in place, a concurrent reader always sees either the old chain or the new one, never a partially updated one. Growth ("resize") happens when the number of entries owned by a given lock exceeds a computed budget; the resizing thread acquires every lock, once, in a fixed order to avoid deadlock, builds a larger bucket array, and rehashes all entries into it, briefly blocking writers but never blocking readers, since readers don't participate in the locking protocol at all.

private static readonly ConcurrentDictionary<string, Lazy<HttpClient>> Clients = new();

HttpClient GetClient(string name) =>
    Clients.GetOrAdd(name, key => new Lazy<HttpClient>(() => CreateClient(key))).Value;

The cost of all this is memory and write overhead: the lock array, the per-lock counters, and node objects that are individually heap-allocated (unlike Dictionary<TKey, TValue>'s compact struct array) make ConcurrentDictionary<TKey, TValue> noticeably heavier per entry than a plain Dictionary<TKey, TValue> guarded by your own lock for single-threaded or low-contention scenarios — it earns its keep specifically under concurrent read/write access, not as a default drop-in replacement.

What interviewers look for: the lock-striping model specifically (not "it locks the whole dictionary"), an understanding that reads are lock-free, and awareness that GetOrAdd's factory delegate can run more than once under contention if two threads race for the same missing key — only one result is kept, but both factories may execute, so the factory must be side-effect-free or idempotent.

• Common mistakes: assuming GetOrAdd's factory is guaranteed to run exactly once per key under concurrent calls; reaching for ConcurrentDictionary<TKey, TValue> by default for state that's actually only ever touched by one thread at a time.
• Follow-up questions: why does Count on a ConcurrentDictionary<TKey, TValue> require taking every lock, and what does that imply about calling it in a hot path? How would you implement an atomic read-modify-write update using AddOrUpdate?

Q6 What are frozen collections, and when do they beat both a mutable collection and an immutable one?#

Short answer: FrozenDictionary<TKey, TValue> and FrozenSet<T> in the System.Collections.Frozen namespace trade a comparatively expensive, one-time construction step for the fastest possible read performance afterward, by analyzing the actual key set at creation time and building a specialized layout for it — the right choice for data that's built once and then read extremely often for the life of the process.

Both types are immutable after construction, created via ToFrozenDictionary()/ToFrozenSet() extension methods rather than a public constructor, and are explicitly optimized for TryGetValue and Contains speed over creation speed — building a FrozenDictionary costs meaningfully more than building an equivalent Dictionary<TKey, TValue>, because it can choose an internal layout (and, for some key distributions, hashing strategy) tailored to the specific keys it was given, something a general-purpose Dictionary can't do since it must support ongoing mutation. That makes them a strong fit for long-lived, read-mostly data such as a routing table, a configuration lookup, or a static list of feature flags loaded once at startup, and a poor fit for anything rebuilt frequently, where the construction cost would dominate.

private static readonly FrozenDictionary<string, PermissionLevel> Roles =
    LoadRoleDefinitions().ToFrozenDictionary(r => r.Name, r => r.Level, StringComparer.OrdinalIgnoreCase);

Immutable collections (System.Collections.Immutable — ImmutableDictionary<TKey, TValue>, ImmutableList<T>, and friends) solve a different problem: they support efficient, safe mutation that produces a new collection while leaving the original untouched, using a persistent, tree-based structure with structural sharing so a "changed" copy doesn't have to duplicate the entire collection. That's ideal for scenarios where you're publishing a new version of shared state repeatedly — configuration that's reloaded periodically and swapped in atomically — and other threads may still be reading the old version concurrently and safely. It's a poor fit for a build-once, read-forever workload, where its per-operation overhead relative to a plain Dictionary<TKey, TValue> buys you nothing, since you're never mutating it after the first build. The three-way choice comes down to this: mutate frequently and share the mutable instance with careful locking, use Dictionary/HashSet; publish new immutable versions repeatedly, use System.Collections.Immutable; build once and read relentlessly, use System.Collections.Frozen.

What interviewers look for: the distinction between "immutable and efficient to change" (the Immutable namespace) and "immutable and optimized purely for reading" (Frozen), since confusing the two leads to picking Frozen for something that's rebuilt on every request — which is strictly worse than just using a Dictionary.

• Follow-up questions: why would you never call ToFrozenDictionary() inside a per-request code path? What data structure would you reach for if you needed both frequent updates and very fast concurrent reads?

Q7 Given a workload description, how do you choose the right collection? Walk through a few concrete scenarios.#

Short answer: Start from the operations you actually need — membership test, key lookup, ordered iteration, index access, or concurrent mutation — because that narrows the field before performance enters the conversation at all; only then weigh presizing, comparer choice and mutation frequency.

A request-deduplication filter that only needs "have I seen this ID before" is a HashSet<T>, not a Dictionary<TKey, bool> — no wasted value slot, and the set-algebra API is a bonus if you ever need to diff two batches. A leaderboard that needs "top N by score" with frequent score updates is a SortedSet<T> (or SortedDictionary<TKey, TValue> keyed by a composite score-then-ID key to avoid duplicate-key issues when two entries tie), because you need ordered iteration and efficient rebalancing on every update — a List<T> re-sorted after each change would be O(n log n) per update instead of O(log n). A static routing table or permission map loaded once at startup and then read on every request for the life of the process is a FrozenDictionary<TKey, TValue> — pay the construction cost once, get the fastest possible lookups for millions of subsequent reads. A per-request cache of expensive computations shared across concurrently executing requests within a single process is a ConcurrentDictionary<TKey, TValue> with GetOrAdd, accepting its per-entry overhead in exchange for lock-free reads under real concurrent access. An in-order event log that's appended to constantly and occasionally needs "give me everything after timestamp X" is well served by a SortedList<TKey, TValue> only if inserts are rare relative to reads — if inserts arrive continuously and out of order, a tree-based SortedDictionary<TKey, TValue> avoids the O(n) shifting cost SortedList would pay on almost every insert.

What interviewers look for: working from required operations to a data structure, not the reverse, and comfort naming the Big-O cost of the operation that matters most for each scenario, since that's usually what separates "technically works" from "will still be fast at ten times the data volume."

• Follow-up questions: how would your leaderboard answer change if ties needed to preserve insertion order? What would you reach for if the routing table above needed to be reloaded every few minutes instead of once at startup?

Q8 What does presizing a collection actually save, and how do you decide on an initial capacity?#

Short answer: Presizing avoids the repeated allocate-and-copy cycles a collection pays as it grows from empty to its final size, turning O(log n) reallocations (each an O(n) copy) into a single upfront allocation — worth doing whenever the final or approximate size is known before the collection is populated.

Both List<T> and Dictionary<TKey, TValue> (and HashSet<T>) accept a capacity in their constructor, and Dictionary/HashSet/List all expose EnsureCapacity(int) for when the size becomes known partway through construction. Presizing to the exact known final count is the easy case — loading n rows from a query into a List<T>(n). When the size is only approximately known, it's almost always better to overestimate slightly than to underestimate: an oversized collection wastes some memory until you optionally call TrimExcess(), while an undersized one still pays for at least one grow-and-copy cycle, which is exactly the cost presizing was meant to avoid. The savings are largest for large collections built in a tight loop — the difference is negligible for a handful of elements, but very real for tens of thousands, where each doubling copy touches every element built so far.

// rows.Count is known up front from the query result — pass it straight through.
var orders = new List<Order>(rows.Count);
var byId = new Dictionary<Guid, Order>(rows.Count);
foreach (var row in rows)
{
    var order = Map(row);
    orders.Add(order);
    byId[order.Id] = order;
}

What interviewers look for: recognizing presizing as a targeted fix for a specific, measurable cost (reallocation and copying), not a blanket "always specify a capacity" habit, and knowing that overestimating is safer than underestimating when the exact count isn't available.

• Common mistakes: presizing every collection defensively regardless of whether its size is knowable, which mostly just adds noise; forgetting that a Dictionary<TKey, TValue>'s capacity constructor rounds up to the next prime bucket size internally, so the requested number and the actual allocated size differ.
• Follow-up questions: how would you presize a collection being filled from an IAsyncEnumerable<T> where the count isn't known ahead of time?

Q9 What goes wrong when a custom IEqualityComparer<T> is inconsistent, or a key is mutated after insertion?#

Short answer: Both bugs have the same root cause — the dictionary or set trusts that a key's hash code and equality never change after it's stored — and both produce the same symptom: the entry is still in the collection, consuming memory, but TryGetValue or Contains can no longer find it, because a lookup recomputes the hash from the key's current state and walks the wrong bucket.

An IEqualityComparer<T> has a contract, not just a suggestion: if Equals(a, b) returns true, then GetHashCode(a) and GetHashCode(b) must be equal. A comparer that violates this — for example, one that compares two floating-point values with a tolerance in Equals but computes GetHashCode from the raw bit pattern — will place logically-equal keys in different buckets, so a lookup for a value "equal to" a stored key can miss it entirely, and worse, Add won't detect the duplicate and will happily insert a second entry that's logically the same key. Mutating a key in place after insertion causes an almost identical failure: the entry stays physically in the bucket its original hash code mapped to, but a subsequent lookup computes the hash from the current, mutated state and walks a different bucket, so the entry becomes unreachable by key even though foreach over the collection still finds it sitting there. This is exactly why mutable reference types with settable fields that participate in GetHashCode make risky dictionary and set keys, and why records used as keys should rely on immutable, init-only properties.

// Dangerous: OrderKey is mutable, and its GetHashCode depends on Region.
public sealed class OrderKey
{
    public string Region { get; set; } = "";
    public Guid OrderId { get; set; }
    public override int GetHashCode() => HashCode.Combine(Region, OrderId);
    public override bool Equals(object? obj) =>
        obj is OrderKey k && k.Region == Region && k.OrderId == OrderId;
}

var byKey = new Dictionary<OrderKey, Order>();
var key = new OrderKey { Region = "EU", OrderId = orderId };
byKey[key] = order;
key.Region = "US"; // byKey[key] can no longer find the order — it's in the "EU" bucket.

What interviewers look for: the specific causal chain — wrong bucket, not "the dictionary is broken" — and the discipline of treating anything used as a dictionary or set key as effectively immutable for the lifetime it participates in the collection.

• Common mistakes: overriding Equals without overriding GetHashCode (or vice versa), which the compiler warns about but doesn't prevent; using a mutable class with default reference equality as a key and being surprised when two "equal-looking" instances don't collide, when in fact no custom equality was ever defined.
• Follow-up questions: why does the C# compiler warn, but not error, when you override Equals without GetHashCode? How would record types help avoid this class of bug?

Q10 What happens if you modify a collection while enumerating it, and why does .NET detect this instead of silently corrupting state?#

Short answer: Most mutable BCL collections track a version counter that increments on every structural change — add, remove, resize — and the enumerator captures that version when it starts; if the version changes mid-enumeration, the next MoveNext() throws InvalidOperationException rather than continuing to walk a data structure that's shifted underneath it.

The failure mode being prevented is worse than an exception: foreach over a List<T> compiles to an index-based walk against the backing array, so a Remove during iteration shifts every subsequent element down by one, and the loop — which just advances its index — silently skips an element, without any error at all. For a Dictionary<TKey, TValue> or HashSet<T>, mutation during enumeration can invalidate the chain the enumerator is mid-walk through, which could, in principle, manifest as skipped entries, duplicate entries, or worse depending on exactly what changed. The version check turns this class of bug from silent and data-dependent into an immediate, loud, reproducible exception — a deliberate fail-fast design, and one explicitly documented as best-effort rather than a hard guarantee: it's reliable for single-threaded modify-during-iterate bugs, but it is not a substitute for actual thread synchronization when multiple threads might mutate and enumerate concurrently, where the outcome is officially undefined and a ConcurrentDictionary<TKey, TValue> or explicit locking is the correct tool instead.

foreach (var (key, value) in cache)
{
    if (IsExpired(value))
    {
        cache.Remove(key); // throws InvalidOperationException on the next MoveNext()
    }
}

// Correct: collect first, then mutate — or enumerate a snapshot.
foreach (var key in cache.Keys.Where(k => IsExpired(cache[k])).ToList())
{
    cache.Remove(key);
}

What interviewers look for: understanding that the version check is a deliberate fail-fast safety net for single-threaded misuse, not a concurrency control mechanism, and knowing the standard fix (materialize the keys to remove first, then mutate) rather than reaching for a lock as the first instinct in single-threaded code.

• Follow-up questions: why doesn't the version check catch every possible concurrent modification? How would Dictionary<TKey, TValue>.Keys.ToList() before the loop change the allocation profile compared to the fix above?