A delivery robot reports the grid squares it drives through, and you want the distinct squares in a set. With a plain dataclass, that fails:
from dataclasses import dataclass
@dataclass
class Point:
x: int
y: int
visited = {Point(0, 0), Point(0, 1)} # raises TypeError (unhashable type: 'Point')
Numbers, strings and tuples can go in a set. This Point cannot, because
it has no hash.
A set finds items by their hash
A hash is an integer that hash() computes from an object's value.
Equal values give equal hashes:
print(hash((0, 1)) == hash((0, 1))) # True
print(hash("abc") == hash("abc")) # True
A set stores each item in a slot that its hash picks. To check
item in visited, Python computes hash(item), looks only at the items in
that slot, and compares them with ==. So a lookup takes about as long in
a set of a million items as in a set of ten. Dictionary keys work the same
way. An object that has a hash is hashable.
The lookup works only if one rule holds. Objects that are equal must have equal hashes. If two equal points had different hashes, the set would look in the wrong slot and miss the point it holds.
Why a plain dataclass has no hash
By default, an object's hash comes from its identity, so two separate
objects get different hashes. The dataclass __eq__ compares fields
instead, so two separate Point(0, 0) objects are equal. Identity hashes
would break the rule.
So when a class defines __eq__ and no __hash__, Python sets __hash__
to None, and hash() raises TypeError. A dataclass with the default
options does the same:
from dataclasses import dataclass
@dataclass
class Point:
x: int
y: int
print(Point.__hash__) # None
There is a second reason. The fields of a plain dataclass can change, and a hash computed from them would change with them. A set does not notice when an item changes. It keeps the item in the slot for the old hash, where a lookup for the new value never looks.
frozen=True gives a dataclass a hash
The fields of a frozen dataclass cannot change after construction. So the
decorator writes a __hash__ that hashes the fields together, and equal
points get equal hashes:
from dataclasses import dataclass
@dataclass(frozen=True)
class Point:
x: int
y: int
visited = {Point(0, 0), Point(0, 1), Point(0, 0)}
print(len(visited)) # 2
print(Point(0, 1) in visited) # True
The two Point(0, 0) objects are separate objects. They are equal and have
equal hashes, so the set keeps one of them.
Common mistakes
Adding unsafe_hash=True to make the error go away. It gives a hash to
a class whose fields can still change. Change a field of a stored object,
and the set loses it:
from dataclasses import dataclass
@dataclass(unsafe_hash=True)
class Spot:
x: int
y: int
spot = Spot(0, 0)
seen = {spot}
spot.x = 5
print(spot in seen) # False
print(Spot(5, 0) in seen) # False
Use frozen=True instead.
Adding eq=False. The class gets the identity hash back, so it goes in
a set. But now Point(0, 0) == Point(0, 0) is False, and a set of
visited points keeps every copy.
Freezing a record that holds a list. A list has no hash, so hashing the
record raises TypeError: unhashable type: 'list'. Store a tuple instead.
Check your understanding
You use frozen Point objects as dictionary keys. Later you build a new Point(2, 3) and look it up. Does it find the entry stored under an earlier Point(2, 3)?
Show answer
Hide answer
Yes. The new point equals the stored key, and equal frozen dataclasses have
equal hashes. The dictionary computes the hash, looks in that slot, and
confirms the match with ==. It does not matter that the two keys are
different objects.
Going further
- The rules for
eq,frozenandunsafe_hashtogether make a small table. The exercise Predict Which Dataclasses Are Hashable works through it. - Python gives string hashes a random starting value each time it starts, so the same string hashes differently in two runs. Never save a hash to a file or a database as an ID.
The __hash__ reference
states the equal-hash rule.