Identity, equality and hashing
When two objects are the same object, and when they are equal.
01The intuition
The problem it solves
A restaurant waitlist stores parties in a list and in a set. A party is a class with a name and a size. The program removes a party by creating a new Party("Rao", 4) and calling remove, and nothing is removed, because two objects with the same fields are not equal unless you say so. Later someone adds equality by fields, and now two different Rao families of four are the same party and one of them never gets a table.
class Party:
def __init__(self, name: str, size: int) -> None:
self.name, self.size = name, size
waiting = {Party("Rao", 4)}
waiting.discard(Party("Rao", 4)) # does nothing: different objects
print(len(waiting)) # 1
# "fix": equality by fields -> now two Rao families of four collide
Build it one piece at a time
Step one: decide for each class whether it is an entity or a value. An entity is a particular thing that persists and changes (this party, this booking); two entities are the same only if they have the same identity. A value is described entirely by its fields (a money amount, a date range); two values with equal fields are interchangeable.
import itertools
from dataclasses import dataclass
_ids = itertools.count(1)
class Party: # entity: identity, not fields
def __init__(self, name: str, size: int) -> None:
self.id = next(_ids)
self.name, self.size = name, size
def __eq__(self, other: object) -> bool:
return isinstance(other, Party) and other.id == self.id
def __hash__(self) -> int:
return hash(self.id)
@dataclass(frozen=True)
class TableSize: # value: fields are everything
seats: int
Step two: whatever you use for equality must not change while the object is inside a set or a dictionary, because the container filed it by its hash. Entities should hash their id and nothing else; values should be immutable.
rao = Party("Rao", 4)
waiting = {rao}
rao.size = 5 # fine: hash uses id, not size
waiting.discard(rao) # removes it
assert TableSize(4) == TableSize(4) and hash(TableSize(4)) == hash(TableSize(4))
Step three: make the identity usable from outside. APIs take and return ids, so a client can say "party 17 left" without holding the object, and the id survives being written to a file or sent over a network.
class Waitlist:
def __init__(self) -> None:
self._parties: dict[int, Party] = {}
def join(self, name: str, size: int) -> int:
p = Party(name, size); self._parties[p.id] = p; return p.id
def leave(self, party_id: int) -> None:
if party_id not in self._parties: raise KeyError(party_id)
del self._parties[party_id]
Why it works
The principle: equality is a design decision, not a default, and it must match what the object means. The invariant is that if two objects are equal they have equal hashes, and that the fields used for both never change while the object sits in a hashed container. Where it breaks: equality by fields on an entity (two bookings for the same room and date become one), a mutable key, an id generated by a counter that restarts when the program restarts, and ids that leak meaning (sequential ids reveal volume, or encode a type that later changes). Interviewers test by asking how you tell two parties apart and whether your objects can be dictionary keys.
The trade-off you must say out loud
Giving everything an id adds a field and a generator, and a counter is not enough once objects are created on several machines or must be unique across restarts, which is where UUIDs or a time-plus-sequence scheme come in. Value objects as frozen dataclasses are nearly free and prevent a whole class of bugs. The follow-up is usually what the id should be: integer, UUID, or a natural key such as an email, and why natural keys are risky when they can change.
Where it shows up in the 100 Google problems
- Restaurant waitlist: the example above; one person holding several reservations is only possible once party and person are separate entities.
- LRU cache: keys must be hashable and immutable or the map and the recency list disagree.
- Hash map from scratch: the equal-hash invariant is the whole design.
- Set with O(1) getRandom: the index map relies on element equality being stable.
- Poker game: a card is a value (two aces of spades are equal); a player is an entity.