`Dictionary<TKey, TValue>` Hash Table & Entry Chaining Internals

1Concept

In .NET, `Dictionary<TKey, TValue>` uses two arrays: `int[] _buckets` and `Entry[] _entries`. Keys are mapped to buckets via `hashCode % primeCapacity`. Collisions are resolved using non-allocating linked list indices.

2Architecture Diagram

Key ──> GetHashCode() ──> Bucket Index = (HashCode & 0x7FFFFFFF) % PrimeSize
                               │
                               ▼
        _buckets[Index] ──> Index into `_entries[i]` (Contains Key, Value, Next Index)

3Code Example

using System;
using System.Collections.Generic;

public class DictionaryInternalsDemo
{
    public static void Main()
    {
        // Pre-allocated dictionary with prime capacity
        var dict = new Dictionary<string, int>(capacity: 100, StringComparer.Ordinal)
        {
            ["AuthToken"] = 9021,
            ["SessionId"] = 4410
        };

        if (dict.TryGetValue("AuthToken", out int token))
        {
            Console.WriteLine($"Found Token in O(1): {token}");
        }
    }
}

4Expected Output

Found Token in O(1): 9021

5Key Takeaways

• ✓Always specify `StringComparer.Ordinal` for ASCII/machine string keys for 3x faster hash comparisons.
• ✓Use `TryGetValue()` to avoid double lookups (`ContainsKey()` + `dict[key]`).
• ✓Use `CollectionsMarshal.GetValueRefOrAddDefault` (.NET 6+) for zero-lookup dictionary mutations.