What happens to a hash-table entry when the key object's fields change after insertion?

## The promise a hash table makes A hash table stores an entry by turning its key into a number and using that number to pick a slot: `bucket = hash(key) mod capacity`. Lookup repeats the same arithmetic on the probe key, walks only that one bucket, and confirms a match with an equality comparison. That is the whole trick, and it is why lookup is expected O(1) rather than O(n) — the table never searches the other buckets. The trick rests on one silent assumption: **the number a key produces today is the number it produced when it was stored.** Nothing in the machinery checks that assumption. ## The two moments a bucket index is computed There are exactly two: insert and lookup. There is no third moment where the table walks its contents asking whether each key still hashes to the bucket it lives in — that would cost O(n) and defeat the point of the structure. A key object is not a broadcast source either: mutating one of its fields fires no notification, sets no dirty bit, and reaches no data structure that happens to be holding it. So when a key mutates after insertion, the entry does not move, and it does not disappear. It becomes **stranded**: physically present in a bucket that no longer corresponds to its own value. ## What it looks like when it bites A route-planning tool keeps a visited-set of waypoint objects keyed by latitude and longitude, so that a waypoint already processed is skipped. Later someone adds a normalization pass that snaps coordinates onto a grid and rewrites them *in place*. Every waypoint recorded before the pass is now stranded. The symptoms an engineer actually sees: - **Lookups miss.** `contains(waypoint)` answers false for a waypoint the set is holding, so the tool reprocesses work it already did. - **Size grows past the number of distinct items.** Re-adding the "missing" waypoint hashes to the new bucket, finds nothing there, and stores a second entry. The set now holds two elements that compare equal to each other — a state the structure is supposed to make impossible. - **Iteration still shows everything.** Iteration walks buckets or slots directly and never hashes anything, so the stranded entry is right there in the dump. That contrast — "I can see it when I print the table, but `contains` says no" — is the diagnostic fingerprint of a mutated key. - **Nothing throws.** No exception, no warning, no corrupted memory. The table's own invariants are intact; it is the relationship between the table and the key that broke. ## Does anything heal it? A common hope is that the next growth-and-rehash pass fixes things. It depends on a degree of freedom implementations differ on: a table that **stores each entry's hash alongside the entry** (a very common optimization, since it makes rehashing and equality short-circuiting cheap) will re-place the entry using the stale stored number and keep it exactly as stranded. A table that **recomputes the hash from the key during resize** will relocate the entry to a bucket consistent with its current values — at which point it may silently become findable again, and any duplicate you inserted meanwhile becomes visible as a real duplicate. Behaviour that changes depending on how full the table happens to be is worse than a consistent failure, not better. Never rely on a rehash to repair a mutated key. ## Which mutations are actually dangerous Only fields that participate in the key's hash or its equality comparison. A waypoint's `label` or `lastViewedAt`, if neither the hash nor equality reads them, can change freely while the object sits in a table — the placement stays correct and probes still match. This is what makes the bug so slippery: the same object is a perfectly safe key until someone adds one field to the hash, or mutates one field that was already in it. Note also that the danger runs the other way for equality-only fields. If equality reads a field the hash ignores, mutation does not strand the entry, but a probe that used to match may stop matching inside the right bucket — the lookup still fails, just for the other half of the contract. ## The rule to state out loud **A key's identifying state must be frozen for as long as it is a key.** Either the type cannot change (identifying fields set once, never rewritten), or you copy those fields into something that cannot change before handing it to the table. Anything else — a comment, a code-review convention, an intention not to mutate — is not a defense, because the failure it prevents is silent and shows up far from the mutation that caused it.