HashMap Key Equality Contract

Java `HashMap` relies on a key's `equals` and `hashCode` methods to locate entries correctly. Keys that are equal must produce the same hash code, and violating this contract can make lookups fail even when an apparently equivalent key is used.

When a key is inserted into a `HashMap`, Java uses the key's `hashCode()` to determine which bucket to inspect. If multiple keys map to the same bucket, `equals()` is used to distinguish the actual key from other keys in that bucket.

The essential contract is: whenever `a.equals(b)` is `true`, `a.hashCode()` must equal `b.hashCode()`. The reverse is not required: two unequal objects may have the same hash code because hash collisions are allowed.

For a custom key class, overriding `equals()` without consistently overriding `hashCode()` can cause a lookup to search the wrong bucket. The map may therefore contain an entry that cannot be found using a logically equal key.

Keys should also avoid changing fields that participate in `equals()` or `hashCode()` while they are stored in a map. If such a field changes, the key's hash may no longer correspond to the bucket where the entry was originally placed.

The contract is about logical equality, not object identity. A well-designed value-like key compares the same state in both `equals()` and `hashCode()`, so objects representing the same key behave consistently in the map.

Key points

• Equal keys must have identical hash codes.
• Equal hash codes do not imply that keys are equal.
• `HashMap` uses hashing to narrow lookup to a bucket and equality to identify the key.
• If a key's equality-relevant state changes after insertion, lookup behavior can break.
• Override `equals()` and `hashCode()` together when defining logical key equality.

Interview questions

Why must a `HashMap` key override `hashCode()` when it overrides `equals()`?

`HashMap` uses `hashCode()` to determine where to look for a key and `equals()` to verify the matching key. If two objects are equal but have different hash codes, they can be assigned to different buckets. A lookup using the equal object may then fail to find the existing entry. Therefore, equal objects must always return the same hash code.

Can two different keys have the same `hashCode()`?

Yes. Hash codes have a finite range, while there can be far more possible objects, so collisions are expected. `HashMap` handles collisions by checking equality among candidates in the relevant bucket. Therefore, a hash collision is valid as long as `equals()` correctly distinguishes unequal keys.

What can go wrong if a mutable key changes after being inserted into a `HashMap`?

If a field used by `equals()` or `hashCode()` changes, the key may acquire a different hash code after insertion. The entry remains associated with its original bucket, while a later lookup may calculate a different bucket. The entry can therefore become effectively unreachable through normal key lookup. Immutable key state is a common way to avoid this problem.

If `a.hashCode() == b.hashCode()`, must `a.equals(b)` return true?

No. Equal hash codes do not imply equality. Different objects are allowed to collide because the hash code compresses a larger set of possible objects into a finite set of integer values. `HashMap` therefore uses `equals()` after hashing to determine whether a candidate key actually matches.

How would you design a custom Java class intended to be used as a `HashMap` key?

I would define a clear notion of logical equality and use exactly the same equality-relevant state when computing the hash code. I would implement `equals()` according to Java's equality contract and override `hashCode()` consistently. I would also make the relevant state immutable, or otherwise guarantee it does not change while the object is a key. Finally, I would test equal instances, unequal instances, collisions, and map retrieval behavior.