skip to content

A C# Dictionary<Sku, int> stops finding an entry after code changes a property on the Sku key object — why, and how do you prevent it?

level: seniorimportance: should knowfreq 60%

answer

  1. the hash is stored at insertion
  2. bucket chosen once
  3. enumeration still shows it
  4. init-only, readonly, or remove first

basics

~20 s

Dictionary<TKey,TValue> stores each key's hash code when it is added and files the entry under that hash. Mutating a field that feeds GetHashCode leaves the entry under the old hash, so lookups and Remove miss it; make key members immutable.

solid answer

~40 s

On `Add` or the indexer setter, `Dictionary<TKey,TValue>` computes the key's hash, chooses a bucket from it and stores the hash in the entry. A lookup recomputes the probe's hash and compares stored hash codes before calling `Equals`. After `sku.Size` changes, looking up the same object yields a new hash that does not match the stored one, and looking up a fresh `Sku` with the old values matches the hash but fails `Equals` against the mutated key. So `ContainsKey` and `Remove` return `false`, `Count` still includes the entry, enumeration still shows it, and `stock[sku] = 3` adds a second entry for the same object. Resizing and `TrimExcess` reuse the stored hashes, so nothing heals it. Prevent it with get-only or `init` key members, or remove the entry before mutating and re-add it after.

code

csharp · 23 lines
csharp
var stock = new Dictionary<Sku, int>();
var sku = new Sku { Code = "SKU-42", Size = "M" };
stock[sku] = 10;

sku.Size = "L"; // the key object is mutated after insertion

Console.WriteLine(stock.ContainsKey(sku));                                      // False
Console.WriteLine(stock.ContainsKey(new Sku { Code = "SKU-42", Size = "M" }));  // False
Console.WriteLine(stock.Remove(sku));                                           // False
Console.WriteLine(stock.Count);                                                 // 1
foreach (var (key, qty) in stock) Console.WriteLine($"{key.Code}/{key.Size}: {qty}"); // still there

stock[sku] = 3;              // adds a second entry for the same object
Console.WriteLine(stock.Count); // 2

sealed class Sku
{
    public string Code { get; set; } = "";
    public string Size { get; set; } = "";
    public override bool Equals(object? obj) =>
        obj is Sku other && Code == other.Code && Size == other.Size;
    public override int GetHashCode() => HashCode.Combine(Code, Size);
}

go deeper

for a junior

Recall that a dictionary key's fields used for hashing must not change after the key is added, or the entry can no longer be found.

for a middle

Explain that Dictionary stores the hash at insertion and compares stored hashes before Equals, and predict what ContainsKey, Remove and the indexer do after the key changes.

for a senior

Diagnose it from symptoms, Count and enumeration seeing what lookups miss, prove it with a linear Equals scan, and fix it with init-only members, an immutable key type, or remove-then-re-add.

for a principal

Make key immutability a design rule: types used as keys expose no setters on hashed members, and reviews treat mutable key types as a defect.

## What Dictionary<TKey,TValue> remembers about a key `Dictionary<TKey,TValue>` is a hash table. Its internal `Entry` records hold the key, the value, a link to the next entry in the same bucket, and the key's **hash code as it was computed at insertion**. Insertion runs: 1. Call the comparer's `GetHashCode(key)`; with no comparer supplied that is `EqualityComparer<TKey>.Default`, which calls the key's own `GetHashCode`. 2. Map the hash to a **bucket**. 3. Store the entry, including that hash code, in the bucket's chain. A lookup (`ContainsKey`, `TryGetValue`, the indexer getter, `Remove`) recomputes the probe key's hash, goes to that hash's bucket, and for each entry checks `entry.hashCode == hashCode && comparer.Equals(entry.key, key)`. The stored hash is never recomputed from the key on lookup. ## What a mutation does Suppose `Sku.Equals` and `Sku.GetHashCode` both use `Code` and `Size`, and after `stock[sku] = 10` some code runs `sku.Size = "L"`. The dictionary still holds the same object, but the entry is filed under the hash of `("SKU-42", "M")`. | Operation after the mutation | What happens | Result | |---|---|---| | `ContainsKey(sku)` with the mutated object | new hash, unless the two hashes happen to coincide, no stored hash matches | `False` | | `ContainsKey(new Sku { Code = "SKU-42", Size = "M" })` | old hash matches, `Equals` against the mutated key fails | `False` | | `Remove(sku)` | same miss as the lookup | `False`, entry stays | | `Count` and `foreach` | the entry is still in the arrays | counted and enumerated | | `stock[sku] = 3` | lookup misses, so a new entry is added | two entries for one object | The dictionary is now internally inconsistent without any exception. Growing it does not repair anything: `Resize` and `TrimExcess` rebuild the buckets from the **stored** hash codes, and so does the copy constructor `new Dictionary<Sku, int>(stock)` when both dictionaries use the same comparer. (The one exception in the source is a string-keyed dictionary switching to a randomized comparer, which recomputes string hashes; it does not apply to a `Sku` class.) `HashSet<T>` stores hash codes the same way and fails the same way. ## Diagnosing it in a running system - The symptom pattern is distinctive: `Count` and enumeration show the item, `ContainsKey` and `TryGetValue` do not. - A linear scan such as `stock.Keys.Any(k => k.Equals(sku))` finds what the hashed lookup cannot, because it calls `Equals` directly without hashing. - Search for setters on the key type's members that feed `GetHashCode`, and for code that edits key objects obtained from `Keys` or from enumeration. - A debugger view of the dictionary shows the entry with its value, which makes the problem look like a lookup bug rather than a key bug; check the key's current fields against the ones it was added with. ## Preventing it 1. **Make the key's identity immutable.** Declare the members that feed `Equals` and `GetHashCode` as get-only or `init`-only properties, or `readonly` fields, so they cannot change after the object initializer finishes. A `private set` still allows the type's own methods to change them, and `required` only forces a value at creation; neither prevents later assignment. 2. **Key by an immutable value.** Use the SKU's code string, an `int` id, or a small `readonly struct` that implements `IEquatable<T>`, and keep the mutable object as the value. 3. **If a key must change, re-key it.** Remove the entry before the mutation, while its hash still matches, then add it again afterwards. 4. **Hash only the stable part.** If some members must stay mutable, leave them out of both `Equals` and `GetHashCode`. 5. **Records are not automatically safe.** Positional record properties are `init`-only, but a record may still declare settable properties that feed its generated equality; the records material covers that. ## Related lessons The language-neutral version of this failure, and whether caching a hash makes a mutable key safe, belong to the foundations material on hash tables. Supplying an `IEqualityComparer<T>` that hashes only the stable fields is covered with dictionaries and sets. Here the point is what C#'s `Dictionary<TKey,TValue>` stores and which C# declarations stop the key from changing.

  • Why does a fresh `Sku` with the original values not find the entry either?
    Its hash matches the stored one, so the dictionary reaches the entry, but it then calls `Equals` on the stored key, which now holds the new `Size`, against the probe with the old `Size`. That returns `false`, so the lookup moves on. Neither the old values nor the new ones can find the entry once a hashed member has changed.
  • Would copying the dictionary with `new Dictionary<Sku, int>(stock)` repair the entry?
    No. When the source is a `Dictionary<Sku, int>` with the same comparer, the .NET 10 constructor copies the entries with their stored hash codes, so the copy is just as broken. `stock.ToDictionary(kv => kv.Key, kv => kv.Value)` does re-add every key and rehash it, but if the indexer already added a second entry for the same object it throws `ArgumentException`. Either way it is a repair, not a prevention.

  • Dictionary recomputes a key's hash code on every lookup of that entry
  • A resize, TrimExcess or the Dictionary copy constructor rehashes and fixes it
  • A private set on the key property guarantees it never changes
  • The dictionary throws an exception when a key is mutated
  • Overriding GetHashCode correctly is enough to make a mutable key safe