How do you use Dictionary<TKey,TValue> correctly in C#? Explain TryGetValue versus ContainsKey plus the indexer, Add versus the indexer setter, TryAdd and GetValueOrDefault, custom comparers, CollectionsMarshal.GetValueRefOrAddDefault, and whether enumeration order is guaranteed.

1. The data structure

.NET's Dictionary<TKey,TValue> uses separate chaining implemented with arrays (not linked-list nodes):

private int[] _buckets;          // index+1 into _entries for the first entry in each bucket (0 = empty)
private Entry[] _entries;        // all entries, densely packed
private int _count, _freeList, _freeCount, _version;

private struct Entry
{
    public uint hashCode;
    public int next;             // index of next entry in the same bucket chain (-1 = end)
    public TKey key;
    public TValue value;
}

Lookup:

1. hash = comparer.GetHashCode(key) (or a devirtualised default comparer for value types).
2. bucket = hash % _buckets.Length — on 64-bit, computed with a fast modulo multiplier (Lemire's method) since the bucket count is a prime.
3. Follow _entries[i].next along the chain, comparing stored hash codes first, then calling Equals only on matches.

Entries live in one contiguous array, which is cache-friendly and avoids per-entry objects.

2. Resizing

The bucket count is a prime from a precomputed table (3, 7, 11, 17, 23, 29, 37, ... ). When _count reaches the entries array length, the dictionary resizes to the next prime ≥ 2×, allocates new arrays, copies entries, and rehashes (recomputes bucket indexes from the stored hash codes — no GetHashCode calls). Resizing invalidates refs returned by CollectionsMarshal.

3. Removal and the free list

Remove unlinks the entry from its bucket chain and pushes its slot onto a free list (encoded in the next field). The next Add reuses that slot. This is exactly why enumeration order (which walks _entries from 0 to _count) looks like insertion order until removals happen — then new items fill the holes.

4. Hash flooding protection

If an attacker sends many keys with colliding hash codes, chains grow and lookups degrade to O(n) — a denial-of-service attack. Defences in .NET:

• string.GetHashCode() is randomised per process (Marvin hash), so attackers can't predict collisions.
• For performance, Dictionary<string, T> with the default/ordinal comparer starts with a non-randomised fast hash and switches to the randomised comparer if a chain exceeds a collision threshold (100).

Custom comparers with poor GetHashCode (e.g. hashing only the first character) reintroduce the problem.

5. How CollectionsMarshal.GetValueRefOrAddDefault works

It performs the normal lookup; if the key exists, returns ref _entries[i].value; otherwise inserts a new entry with default(TValue) and returns a ref to its value. Because it's a raw ref into the entries array:

• No copy of struct values — you can mutate fields in place.
• No version increment for in-place updates, so enumerators won't detect your change.
• Any later Add/Remove can resize or reuse slots; using an old ref afterwards writes to the wrong place or a stale array.

6. Performance comparisons

For tens of millions of operations, halving lookups is measurable.

7. OrderedDictionary<TKey,TValue> and FrozenDictionary

• .NET 9 added a generic OrderedDictionary<TKey,TValue> that preserves insertion order and supports index access (GetAt(i)), at the cost of O(n) removals.
• FrozenDictionary<TKey,TValue> (.NET 8) analyses keys at construction to pick a specialised strategy (e.g. for small string sets it may hash only some characters or bucket by length). Construction is slower, lookups are faster — ideal for configuration and lookup tables built once at start-up.

Try it yourself

1. Benchmark ContainsKey + indexer vs TryGetValue vs GetValueRefOrAddDefault for a word count over a large text.
2. Add 10 keys, remove 3, add 3 new ones, and print enumeration order.
3. Create a key type whose GetHashCode returns a constant and measure lookups as the dictionary grows.
4. Compare Dictionary vs FrozenDictionary lookup speed for 100 string keys.

using System.Runtime.InteropServices;

var stock = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

// Reads
if (stock.TryGetValue("SKU-1", out int qty))      // one lookup
    Console.WriteLine(qty);
int safe = stock.GetValueOrDefault("SKU-9", 0);    // default instead of exception

// Writes
stock.Add("SKU-1", 5);                // throws if present: duplicates are a bug
stock["SKU-1"] = 7;                   // overwrite: last write wins
bool added = stock.TryAdd("sku-1", 9); // false: same key under OrdinalIgnoreCase

// Counting with one lookup per word
var counts = new Dictionary<string, int>(StringComparer.Ordinal);
foreach (var word in words)
{
    ref int c = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, word, out _);
    c++;
}

// Remove and get the old value in one lookup
if (stock.Remove("SKU-1", out int old))
    Console.WriteLine($"Removed {old}");

// Order-sensitive output
var ordered = new OrderedDictionary<string, int>();   // .NET 9+
ordered.Add("first", 1);
ordered.Add("second", 2);

// Span lookup without allocating (.NET 9+)
var lookup = counts.GetAlternateLookup<ReadOnlySpan<char>>();
ReadOnlySpan<char> line = "apple,banana";
bool hasApple = lookup.ContainsKey(line[..5]);