Equality and hash contracts: make values safe keys

Separate object identity from value equality, then keep equality inputs stable when a value enters a hash-based collection. Relationships and copying · Object-oriented programming.

Two points can carry the same coordinates while remaining two different objects. Put one into a set, edit its coordinates, and the set may still contain it but fail to find it. The missing idea is a contract between equality and hashing. A hash is a number a collection computes from a value to jump straight to one numbered shelf (a bucket) instead of scanning every entry.

Ask identity and value questions separately

Suppose Point(2, 3) is created twice. Identity asks whether both names reach one object. Value equality asks whether the two objects represent the same point according to the type's rule. Those answers can differ: two objects can be equal without being identical, and one object is always identical to itself.

In Java, == compares references for ordinary objects. A value type can override equals so two same-type points with the same coordinates compare equal. In Python, is asks for identity and == asks the objects for their equality behavior. Neither language makes “same displayed fields” a universal rule for every class; the type defines the value boundary.

record Point(int x, int y) {}

Point a = new Point(2, 3);
Point b = new Point(2, 3);
System.out.println(a == b);       // false: distinct objects
System.out.println(a.equals(b));  // true: equal record values

from dataclasses import dataclass

@dataclass(frozen=True)
class Point:
    x: int
    y: int

a = Point(2, 3)
b = Point(2, 3)
print(a is b)  # False: distinct objects
print(a == b)  # True: equal field values

Follow equality into a hash bucket

A hash-based set or map computes the hash from a value's equality fields, jumps to that bucket, and then uses equality to decide whether a candidate key in that bucket matches. The contract is one-way: if a.equals(b) or a == b says the values are equal, their hashes must be equal. The reverse does not hold. Two unequal values can produce the same hash; that collision is expected to be resolved by equality.

For Java, overriding equals generally means overriding hashCode with the same equality inputs. The Object contract also expects the hash to remain stable while those inputs remain unchanged. Python's data model has the same operational rule for dictionary and set keys: equal objects have equal hashes, and the hash must remain stable for the key's lifetime in the collection.

The scenes below draw a table of eight buckets, numbered 0 to 7, with a teaching hash: add an object's integer fields, then take the remainder after dividing by 8. Point(2, 3) and Point(3, 2) both give 5, so they share bucket 5. Typical library hashes of these two points differ, but a hash is allowed to collide. A shared bucket does not make the points equal: the equality check still separates them.

Skip hashCode and the failure is concrete. The inherited hash is identity-based, so two equal values almost always get different hashes (the scene shows 11 and 6; real identity hashes are arbitrary numbers), the lookup visits a different bucket, and it never gets as far as asking equality:

final class Pin {
    final int code;
    Pin(int code) { this.code = code; }
    @Override public boolean equals(Object o) { return o instanceof Pin p && p.code == code; }
}

var pins = new java.util.HashSet<Pin>();
pins.add(new Pin(1));
System.out.println(pins.contains(new Pin(1))); // false in practice

Do not edit a key beneath its collection

Consider a mutable Ticket whose equality and hash use number. In the table model of this lesson, ticket 17 is stored in bucket 1 (17 mod 8). Change its number to 42 without relocating the entry. A lookup with that ticket now hashes 42, goes to bucket 2, and finds nothing. A fresh Ticket(17) goes to bucket 1, but the stored entry no longer compares equal to it, so that lookup misses too. The object was not removed; the key's location and meaning drifted apart. The miss is guaranteed; the bucket picture is only a model, and real collections lay out entries differently.

final class Ticket {
    int number;
    Ticket(int number) { this.number = number; }
    @Override public boolean equals(Object other) {
        return other instanceof Ticket t && number == t.number;
    }
    @Override public int hashCode() { return Integer.hashCode(number); }
}

var map = new java.util.HashMap<Ticket, String>();
var ticket = new Ticket(17);
map.put(ticket, "open");
ticket.number = 42;       // equality input changed while stored
System.out.println(map.get(ticket));          // null
System.out.println(map.get(new Ticket(17)));  // null
System.out.println(map.size());               // 1: still stored

class Ticket:
    def __init__(self, number):
        self.number = number

    def __eq__(self, other):
        return isinstance(other, Ticket) and self.number == other.number

    def __hash__(self):
        return hash(self.number)

ticket = Ticket(17)
records = {ticket: "open"}
ticket.number = 42       # equality input changed while stored
print(records.get(ticket))          # None
print(records.get(Ticket(17)))      # None
print(len(records))                 # 1: still stored

The safer choices are to build equality and hash from the same fields, and to keep those fields immutable or remove a key before changing them. In Python, a class that defines __eq__ without __hash__ gets __hash__ = None, so it cannot be a dict key or set member:

class Mark:
    def __init__(self, n): self.n = n
    def __eq__(self, other): return isinstance(other, Mark) and self.n == other.n

try:
    {Mark(1)}
except TypeError as err:
    print(err)  # unhashable type: 'Mark'

A @dataclass with eq=True and frozen=False does the same; unsafe_hash=True forces a hash and should be a deliberate exception. Records and @dataclass(frozen=True) generate equality and a matching hash together. Java has no automatic equivalent, so its class author must state and enforce any policy that values of the type are not used as hash keys.

When a type should not be a key

A value whose equality inputs must change cannot promise a stable hash. A Python type that sets __hash__ = None refuses the hash path entirely, which is the safer policy for mutable values.

Recap

• Identity asks whether two names reach one object; value equality asks whether a type treats two values as equivalent.
• Equal values must have equal hashes, but unequal values may collide and still need an equality check. A Java class that overrides equals without hashCode misses its own equal values in a HashSet.
• Keep equality inputs stable while a key is stored.
• In Python, choose __hash__ = None when mutable equality inputs should not be hashable. Java must enforce stable inputs or keep the type out of hash collections through its API and design policy.

Continue to immutable value boundaries when a value object contains a list or other mutable descendant. Practise the same equality distinction in Linked List Fundamentals, where equal-looking node values do not make two nodes identical.