Why must two hash-table keys that compare equal also produce the same hash value?
answer
- think about what the table checks first
- equality runs only inside one bucket
- equal keys routed to different buckets — then what?
- lost lookups and duplicate entries in sets
basics
~20 sHash tables find the bucket by hash first and only then compare keys for equality. If equal keys hash differently, a lookup probes the wrong bucket, so a stored entry is never found and a set can silently hold duplicates.
solid answer
~50 sA hash table never scans everything: it computes the key's hash, jumps to that bucket, and runs the equality check only against keys already in that bucket. The rule "equal objects must have equal hashes" exists because equality is consulted only *after* the hash has narrowed the search. Violate it and you get two silent symptoms: lost lookups — insert under one key, look up with an equal key that hashes differently, land in the wrong bucket, get nothing — and phantom duplicates — a hash set stores a second, equal element in another bucket because the two were never compared. The reverse direction is not required: unequal keys may share a hash (a collision), and the equality check exists precisely to resolve those. That is why equality and hashing must always be defined together, over the same fields.
go deeper
Be ready to state the rule — equal keys must hash equal — and name both symptoms: lookups that miss and sets that hold duplicates. Explain that the bucket is chosen by hash before equality is ever consulted.
Explain the two-step lookup precisely and which direction the implication runs: equality constrains hashing, never the reverse. Be able to say why collisions are legal and even a constant hash is contract-correct but slow.
Connect the rule to engineering practice: equality and hashing reviewed as one unit, a property test asserting equal implies equal hash, and why this failure mode slips past tests that only ever reuse a single instance.
Own the team-level discipline: value/key types generated or derived so equality and hashing cannot drift apart, and a review standard that treats a half-overridden pair as a blocking defect rather than a style nit.
## How a hash table actually finds a key A hash table keeps its entries in an array of buckets. Every operation on a key runs the same two-step routine, in strict order: 1. **Route by hash.** Compute the key's hash value and reduce it to a bucket index (typically by masking or taking it modulo the table size). 2. **Confirm by equality.** Inside that one bucket — or along one probe sequence, under open addressing — compare the probe key against the stored keys using the equality check. The order is the whole story. Equality is consulted *only* among keys that already hashed to the same place. The table never asks "is this key equal to anything, anywhere?" — that would be a full O(n) scan, which is exactly what hashing exists to avoid. ## The contract For that routine to be correct, a key type must honor two clauses: - **Equal objects must produce equal hash values.** If two keys compare equal, they must hash identically — otherwise the router and the confirmer disagree about identity. - **A stored key's hash must stay consistent** for as long as the key is in the table (a clause with its own failure stories). Equally important is what the contract does **not** say: unequal objects are allowed to share a hash value. That is a *collision*, it is expected — hash values get compressed into a small number of buckets, so the pigeonhole principle guarantees collisions — and the equality check exists to resolve them. A hash function that returns the same constant for every key is contract-*legal*; it merely degrades every operation to an O(n) scan of one giant bucket. Legality and quality are different axes. ## What breaks, concretely Suppose a key type defines value equality but its hashing does not follow, so two equal keys can return different hashes. - **Lost lookups.** An entry is inserted under key A. A later lookup uses key B, where B compares equal to A but hashes differently. The lookup routes to B's bucket, finds nothing there, and reports absence. The entry exists; it is simply stored where this lookup will never probe. - **Phantom duplicates.** A hash set is a hash table keyed by its elements. Inserting A and then an equal B routes them to different buckets; the set never compares them, concludes B is new, and stores both. The set now violates its own uniqueness promise. Both failures are **silent**. Nothing raises an error and no invariant checker fires — the table faithfully executes its routine on inconsistent answers. The symptoms surface far away, as "the cache never hits", "the dedupe emits duplicates", "the same user appears twice in the report". ## Why the rule is stated as "define both together" Default equality in most environments is identity-based — two references are equal only if they are the same object — and default hashing is derived to match, so the inherited pair is internally consistent. The moment a type redefines equality to mean *value* equality, the inherited hashing is out of step: equal-by-value objects still hash as distinct individuals. Hence the practical rule every codebase enforces: **the equality check and the hash function are one unit — change one, change both, and derive both from the same fields.** Mainstream ecosystems write this into their core contracts — Java's base object specification and Python's data model state, in nearly the same words, that objects which compare equal must hash equal — because every standard hash container silently assumes it. | Situation | Contract | Behavior | |---|---|---| | Equal keys, equal hashes | honored | correct lookups; collisions resolved by equality | | Equal keys, different hashes | **violated** | lost lookups, duplicate set entries | | Unequal keys, equal hashes | honored (collision) | correct, slightly slower bucket scan | | All keys, one constant hash | honored | correct but O(n) — a quality problem, not a contract problem | The table is worth memorizing in shape: the contract runs in one direction only. Equality constrains hashing; hashing constrains nothing about equality.
- Is the reverse required — must unequal keys produce different hash values?No. Unequal keys sharing a hash is a collision, which is expected and legal; the equality check resolves it inside the bucket. Even a constant hash for every key honors the contract — it just collapses the table into one bucket and degrades operations to O(n). Distinctness of hashes is a quality goal, never a correctness requirement.
- If the table already has the hash, why does it bother with equality checks at all?Because a matching bucket proves nothing: hash values are compressed to a small index range, so unequal keys legitimately land together, and even a full 32- or 64-bit hash match can be a collision. Equality is the arbiter of identity; the hash only narrows where to ask the question.
- Why must a type that defines custom value equality redefine its hashing in the same change?Because the inherited default is usually identity-derived: it agrees with identity equality but not with the new value equality. Equal-by-value instances would keep hashing as distinct individuals, breaking the contract. The two functions form one unit computed from the same fields, so a change to either alone is a half-finished key type.
A library shelves books by catalog number and only compares titles within one shelf. If two copies of the same book get different catalog numbers, the librarian looks on the wrong shelf and swears the book was never acquired.
saying these in an interview costs you the question
- The table finds keys by equality alone, so hashing is only a speed optimization
- Equal hash values mean the keys are equal
- Breaking the contract raises an error instead of failing silently
- Distinct keys must be given distinct hash values for correctness