4. Hash tables — how Dictionary works inside

A hash table maps a key to a slot ("bucket") using a hash function:

key "pen" → GetHashCode() = 193410 → 193410 % 8 buckets = bucket 2 → entry ("pen", 10)

Steps for dict["pen"]:

1. Compute hash = key.GetHashCode().
2. bucket = hash % bucketCount.
3. Walk the entries in that bucket comparing hashes and then Equals until found.

Collisions (two keys in the same bucket) are inevitable. Strategies: chaining (each bucket holds a small list — .NET Dictionary uses chaining through an entries array) or open addressing (probe the next free slot). When the table fills up (load factor), it resizes to a larger prime size and re-hashes everything — O(n) once, amortised O(1).

Why Equals and GetHashCode must agree: if two equal keys produce different hashes, they land in different buckets and lookups fail. If a key's hash changes after insertion (mutable key), the entry becomes unreachable.

public record ProductKey(string Sku, int Warehouse);   // records implement value-based Equals/GetHashCode
var stock = new Dictionary<ProductKey, int> { [new("PEN-1", 3)] = 50 };
Console.WriteLine(stock[new("PEN-1", 3)]);            // 50 — found because equal keys hash equally

Classic use — two-sum in O(n):

int[] TwoSum(int[] nums, int target)
{
    var seen = new Dictionary<int, int>();           // value → index
    for (int i = 0; i < nums.Length; i++)
    {
        if (seen.TryGetValue(target - nums[i], out int j)) return [j, i];
        seen[nums[i]] = i;
    }
    return [];
}