What are immutable collections in .NET? Compare ImmutableArray<T>, ImmutableList<T> and ImmutableDictionary<TKey,TValue>, explain builders and structural sharing, and contrast them with ReadOnlyCollection<T>, IReadOnlyList<T> and FrozenDictionary.

1. ImmutableArray<T> internals

public readonly struct ImmutableArray<T> : IReadOnlyList<T>, IImmutableList<T>, IEquatable<ImmutableArray<T>>
{
    internal readonly T[]? array;
}

• A struct with a single field: passing it around costs the same as passing an array reference.
• Indexing and foreach (struct enumerator) are as fast as a raw array; AsSpan() gives a ReadOnlySpan<T>.
• default(ImmutableArray<T>) has a null inner array; most members throw. Check IsDefault/IsDefaultOrEmpty, and initialise fields to [] or ImmutableArray<T>.Empty.
• Equality (==) compares the underlying array reference, not contents. Use SequenceEqual for content comparison — which matters if you put ImmutableArray<T> in records (record equality will be reference-based for that property).
• ImmutableCollectionsMarshal.AsImmutableArray(array) (.NET 8) wraps an existing array without copying — only safe if you never mutate that array again.

2. ImmutableList<T> as an AVL tree

Each node stores the element, left/right children, height and count of nodes in its subtree, which allows O(log n) indexing (list[i] walks left/right using subtree counts). Adding at the end creates a new path of O(log n) nodes and rebalances with rotations, sharing all untouched subtrees with the previous version.

Costs: each element is a node object (~40+ bytes), and reads chase pointers — so ImmutableList<T> is much slower to iterate and index than List<T> or ImmutableArray<T>. It shines only when you make many small updates while needing old versions to remain valid.

3. ImmutableDictionary internals

It's a sorted AVL tree keyed by hash code, where each tree node holds a "bucket" (one value or a small immutable list for collisions). Lookup = hash → O(log n) tree search → compare keys in the bucket. Updates share structure like ImmutableList. Compared with Dictionary (O(1) array buckets), reads are typically several times slower.

4. Builders

A builder holds a mutable version of the same tree (or a List<T>-like buffer for ImmutableArray.Builder). Nodes created by the builder are marked as owned by it and are mutated in place; ToImmutable() "freezes" them, so the builder can reuse untouched nodes and doesn't copy everything. For ImmutableArray.Builder, MoveToImmutable() hands over the internal array without copying when Count == Capacity (otherwise it throws); ToImmutable() always copies.

5. ImmutableInterlocked

ImmutableInterlocked.Update(ref location, transformer) implements a compare-and-swap loop:

do { original = Volatile.Read(ref location); updated = transformer(original); }
while (Interlocked.CompareExchange(ref location, updated, original) != original);

If another writer changed the reference in between, it retries with the new version. The transformer must be pure (it may run multiple times). Helpers exist for dictionaries (AddOrUpdate, GetOrAdd, TryAdd, TryRemove), stacks and queues.

6. Frozen collections internals

ToFrozenDictionary/ToFrozenSet choose among many specialised implementations based on the keys:

• Small collections (≤ ~10): linear scans over arrays can be fastest.
• Integer keys: dense-range or specialised hashing.
• String keys: analyse lengths and character positions to find a subset of characters that uniquely discriminates keys, compute hashes over just that substring, and optionally reject by length first; case-insensitive ASCII-specific variants.

Construction can be 10–50× slower than building a Dictionary, so frozen collections pay off when the lookups per creation are large — typical for start-up-built lookup tables.

7. Choosing

Try it yourself

1. Benchmark lookups in Dictionary, ImmutableDictionary and FrozenDictionary with 1,000 string keys.
2. Benchmark adding 10,000 items one at a time to ImmutableArray (O(n²)), ImmutableList, and an ImmutableArray.Builder.
3. Wrap a list with AsReadOnly(), modify the original list, and observe the wrapper.
4. Implement the atomic snapshot swap with ImmutableInterlocked and hammer it from multiple threads.

using System.Collections.Frozen;
using System.Collections.Immutable;

// 1. A view is not a snapshot
var inner = new List<string> { "a" };
IReadOnlyList<string> view = inner.AsReadOnly();
inner.Add("b");
Console.WriteLine(view.Count);              // 2: the view sees the change

// 2. Immutable: new versions, old ones unchanged
ImmutableList<string> v1 = ["a", "b"];
ImmutableList<string> v2 = v1.Add("c");
Console.WriteLine($"{v1.Count} {v2.Count}"); // 2 3

// 3. ImmutableArray: array-speed reads, build with a builder
var builder = ImmutableArray.CreateBuilder<int>(initialCapacity: 1000);
for (int i = 0; i < 1000; i++) builder.Add(i * i);
ImmutableArray<int> squares = builder.MoveToImmutable();   // no copy
ReadOnlySpan<int> span = squares.AsSpan();

ImmutableArray<int> notSet = default;
Console.WriteLine(notSet.IsDefault);        // true; notSet.Length would throw

// 4. Lock-free shared state
private ImmutableDictionary<string, int> _limits = ImmutableDictionary<string, int>.Empty;

public void SetLimit(string key, int value) =>
    ImmutableInterlocked.Update(ref _limits, d => d.SetItem(key, value));

public int GetLimit(string key) => _limits.GetValueOrDefault(key);  // no lock

// 5. Read-optimised snapshot rebuilt on refresh
private FrozenDictionary<string, bool> _flags = FrozenDictionary<string, bool>.Empty;
public void Refresh(IDictionary<string, bool> latest) =>
    Volatile.Write(ref _flags, latest.ToFrozenDictionary(StringComparer.OrdinalIgnoreCase));