Equality and hashing

Why it matters

Hash maps and sets are the most used data structures in application code, and they trust two methods you write: one that says whether two objects are equal and one that summarises an object as a number. Get either wrong and a set holds duplicates, a cache never hits, or a key you just inserted cannot be found. These bugs are silent, data-dependent and a favourite interview question precisely because they are so easy to write.

The idea

Identity asks "are these the same object?" (== on references in Java, is in Python). Equality asks "do these represent the same value?" (equals in Java, == in Python and C# when overloaded). Two Money objects for 10 euros are equal but not identical. By default, equality falls back to identity; for value-like types you must define it.

The equals contract

The hash contract

A hash table finds an entry by computing the key's hash code, jumping to the bucket for that code, then comparing keys in that bucket with equals. So the rule is: equal objects must have equal hash codes. Unequal objects may share a code (a collision, handled by comparing within the bucket), but too many collisions degrade lookups toward a linear scan.

final class Point {
    private final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;     // also handles null
        return x == p.x && y == p.y;
    }
    @Override public int hashCode() { return Objects.hash(x, y); } // same fields as equals
}

Better still, let the language generate both: Java records, Kotlin data classes, C# records, Python dataclasses with frozen=True, and Rust's derived PartialEq, Eq and Hash all derive equality and hashing from the same fields, so they cannot drift apart.

Mutable keys

If a key's fields change after it is inserted, its hash code changes, but the entry is still filed under the old bucket. Lookups with the same object now search the new bucket and miss; the entry is effectively lost and leaks. Keys in maps and elements in sets should be immutable, or at least never mutated while they are in the collection.

Equality and inheritance

Adding a field in a subclass breaks equality with the parent. A ColoredPoint(1, 2, red) comparing itself only to other colored points, while Point(1, 2) compares only coordinates, makes p.equals(cp) true and cp.equals(p) false: symmetry fails, and sets behave unpredictably depending on insertion order. The robust options are to make value classes final, compare exact classes with getClass() rather than instanceof when subclassing must be allowed, or prefer composition (a ColoredPoint has a Point and a colour).

Special cases worth knowing

Floating-point values compare unreliably after arithmetic; compare with a tolerance outside hash-based collections, and never use computed floats as map keys. Strings compare by value with equals but by identity with == in Java. Entities with a database identity (a User) usually define equality by their stable identifier, not by every field; value objects (Money, Address) define it by all their fields.

Trade-offs

Value-based equality makes objects usable as keys and comparisons meaningful, at the cost of defining and maintaining it correctly. Generated equality (records, data classes) removes most bugs but compares every field, which may be wrong for entities. Identity equality is fast and never wrong for its own purpose, and useless for value types.

In an interview

Show the pairing and immutability together: "OrderLine is a record, so equals and hashCode are generated from the same fields and it is immutable, which makes it safe as a map key. User equality is by user ID only, because two snapshots of the same user with different names are still the same user."