Does caching a key's hash value at construction make a mutable object safe to use as a key?
answer
- ask what half the cache freezes
- placement is only one of two steps
- equality still reads live fields
- two equal objects, two different cached values
- caching buys speed, not safety
basics
~20 sNo. A cached hash freezes where the entry sits, but equality still reads live fields, so keys that now compare equal can carry different cached hashes. Caching is a speed optimization for keys that are already immutable.
solid answer
~50 sNo — caching freezes only half of what a hash table depends on. The cached value keeps a stored entry's bucket stable, but the equality comparison still reads the object's live fields. After a mutation, two objects that now compare equal can carry different cached hashes and land in different buckets, precisely the state the structure forbids. A probe built from the key's current values hashes to a bucket the entry is not in; a probe built from the old values lands in the right bucket and fails the equality check. The map is now broken in both directions instead of one. Caching a hash is a performance technique for keys that are already immutable — it amortizes an expensive computation over many lookups. Freeze both the hash *and* the fields equality reads and you have not saved a mutable key; you have built an immutable one.
go deeper
Know that a hash table uses two things from a key: the hash picks the bucket, and an equality comparison confirms the match. A cached hash only affects the first of those.
Be able to walk the cases out loud — probe with the old values, probe with the new values, probe with the original reference — and show that caching converts one failure mode into two. Then name caching for what it is: an optimization for immutable keys.
Judge when the cache earns its memory: expensive hashes, lookup-heavy workloads, big buckets where the stored value short-circuits comparisons. And insist that it is only ever applied on top of frozen identifying state, never as a mutation defense.
Set the expectation that no fix living inside the key object can repair the table-to-entry relationship. Direct effort at the type contract and the boundary where objects become keys, and treat "we cache the hash" in a design review as a claim to challenge.
## What the cache actually freezes Caching a hash means computing the key's hash value once — at construction, or lazily on first use — and storing it in the object so later lookups reuse it instead of recomputing. It is a real and widely used optimization, particularly for keys whose hash is expensive: long text, deeply nested structures, composite keys built from several fields. But a hash table depends on **two** things from a key, not one: 1. **Placement** — the hash value picks the bucket. 2. **Confirmation** — the equality comparison decides which entry in that bucket is the match. A cache freezes the first. It does nothing at all about the second, because equality is a separate operation that reads whatever the fields currently hold. ## Walking the failure Take a document editor that caches rendered layout keyed by paragraph objects, where a paragraph's hash is derived from its text and style, and equality compares those same fields. A paragraph P is inserted with text `t0`, caching hash `h(t0)`. An edit rewrites P's text in place to `t1`. Now consider each way you might reach the entry: | Probe | Bucket it visits | Equality result | Outcome | |---|---|---|---| | The same object P | bucket of `h(t0)` (cached) | matches itself | found | | A fresh paragraph holding `t1` | bucket of `h(t1)` | would have matched | **miss** — wrong bucket | | A fresh paragraph holding `t0` | bucket of `h(t0)` — correct! | P now holds `t1`, so no match | **miss** — right bucket, failed comparison | That third row is what the cache buys you: instead of one failure mode you now have two. The entry is reachable only by holding the exact original reference, which is not a lookup — it is remembering the answer. Worse, the cross-object invariant is now visibly violated. Two paragraphs that compare **equal** (both holding `t1`: the mutated P, and a fresh one) carry **different** hash values (`h(t0)` and `h(t1)`) and therefore live in different buckets. Any set built on this can hold both, so a structure whose entire contract is "no two equal elements" now holds two. ## "Then recompute the hash on every mutation" This is the next thing candidates reach for, and it fails for the reason the whole leaf turns on: the recomputed value lives in the key object, and the table is still holding the entry in the bucket it picked earlier. Keeping the key's own idea of its hash fresh does not move anything inside the table. Recomputation without notification is strictly worse than caching, because now the entry is stranded *and* the key no longer agrees with the number it was filed under. The general point: no defense that lives inside the key object can work, because the broken relationship is between the table and the entry, and the key has no channel to it. ## When caching a hash is right On keys that are already immutable, it is a clean win: - The hash is computed once and reused across every lookup, insert-collision walk and resize. - It gives a cheap **pre-check** before equality: two entries with different stored hashes cannot be equal, so the expensive comparison is skipped. In a bucket holding several entries this is often the dominant saving. - Resizes get cheaper, since re-placing entries needs no rehashing of key content. Two details worth knowing. First, **lazy** caching (compute on first use, store) needs a way to distinguish "not yet computed" from a legitimately computed value equal to the sentinel — a hash that genuinely comes out as the sentinel gets recomputed on every call, which is a performance bug rather than a correctness one, but a real one on a hot key. Second, in a concurrent setting a lazily filled cache must be safe to publish; that discipline belongs to concurrency, not to key design, but it is why some designs compute eagerly. ## The conclusion to state If you take the cache all the way — freeze the hash **and** compute equality from the same frozen snapshot, so neither can observe a later mutation — you have built an immutable key. That is the actual fix, and it is worth naming as such: the safe pattern is not "cache the hash", it is "make the identifying state unchangeable, and cache the hash because now you can".
- Why doesn't recomputing the key's hash on every mutation fix it either?Because the recomputed value lives in the key, and the entry is still sitting in the bucket the table picked at insert. Nothing propagates. You end up with a key whose fresh hash disagrees with the bucket it was filed under — stranded, plus internally inconsistent.
- When is caching a hash value genuinely worth the memory?On immutable keys with expensive hashes — long text, nested or composite structures — especially when lookups outnumber inserts. Beyond skipping recomputation, the stored value acts as a cheap pre-check: entries with different hashes cannot be equal, so the expensive comparison is skipped during bucket walks and resizes.
- If both the hash and the equality comparison read a frozen snapshot, what have you actually built?An immutable key. That is the point worth landing: the safe pattern is not "cache the hash" but "freeze the identifying state, and cache the hash because you now can". The cache becomes an optimization on top of a correct design instead of a patch over a broken one.
Caching the hash is like laminating the shelf label while leaving the book's title editable. The book stays where the label says; it just is not the book the label describes any more.
saying these in an interview costs you the question
- Claims a cached hash makes any key safe to mutate
- Says recomputing the hash on mutation repairs the entry
- Assumes equality never reads the fields that feed the hash
- Thinks the cache updates itself when a field changes
- Ignores that two equal keys may now carry different cached hashes