Custom keys: __eq__, __hash__ and pair keys in Python

Why this matters

A dict finds a key in two steps. First it computes a whole number from the key, called a hash value. It uses that number to pick a slot to look in. Then it compares the key you gave with the keys already in that slot. Strings, numbers and tuples come with rules for both steps. Your own classes do not have any rules until you write them.

If you use your own object as a key and skip the rules, the dict may fail to find a key that looks the same to you. In Python this often means a plain None from get, or a set that holds two objects that are equal. The program does not crash, so the bug is hard to spot.

This lesson shows how to write the two methods that control this, __eq__ and __hash__. It then shows the simplest tools for keys that hold a few values: dataclasses and tuples. You will also see how a pair of numbers is hashed in practice. Every program below was run, and the output blocks are copied from those runs.

How a dict compares two keys

A dict stores pairs of a key and a value. Python's dict keeps its entries in an internal table of slots. The hash value of a key tells the dict which slot to look in. Inside that slot, the dict calls == on the stored key, through its __eq__ method, to decide whether it is the key you asked for.

Think of a row of mailboxes. The hash value says which mailbox to open. The == check is reading the name on the letter inside to confirm it is the right one. Both steps are needed. If two keys are equal but have different hash values, they go to different mailboxes, and the dict never compares them. That is the whole reason the two methods must agree.

A class with no rules

The first program uses a plain class called Point with two attributes. It does not define __eq__ or __hash__.

get with a new equal point: None
size: 1
set size after adding the same coordinates twice: 2

Without __eq__, Python decides that two objects are equal only when they are the same object in memory. The two Point(1, 2) calls create two different objects, so the lookup finds nothing. The set holds both points because they are different objects, even though their numbers match.

Writing eq and hash

To teach Python that two points with the same numbers are the same key, write two methods. __eq__ answers whether two objects are equal. __hash__ gives a number for the object, and it must be the same for two equal objects.

get with a new equal point: home
get with a different point: None
set size: 1
equal hashes for equal points: True
print of a point: (1, 2)

Some details in this code matter.

__eq__(self, other) receives any object as other. The first check, isinstance(other, Point), makes sure the comparison is with a point before the code reads other.x. Without it, comparing a point with a string would raise an error, as the mistakes section shows.

__hash__ returns hash((self.x, self.y)). The tuple of the two fields gets one hash value, and that value depends on both fields and on their order. The two points (1, 2) and (2, 1) are different keys. The point's hash value is the same for any two points with equal fields, which is what the rule needs.

__repr__ controls how the object prints. It has no effect on the dict, but it makes the output easier to read.

The three rules

Python's documentation for these two methods sets rules. These three cover almost every real case.

1. Two equal objects must return the same hash value. This is the rule the dict depends on most.
2. The hash value of an object must not change while the object is stored as a key. A key whose hash value changes is lost, as the next section shows.
3. __hash__ may use only fields that __eq__ also compares. If __eq__ ignores a field and __hash__ uses it, two equal objects can get different hash values and break rule 1.

Rule 3 is easy to miss. Suppose __eq__ compares row and number, but __hash__ uses number alone. Two equal objects have the same number, so the rule holds. Now suppose __hash__ used a field that __eq__ never looks at. Two objects could be equal and still have different hash values. The dict would then put them in different slots.

__eq__ must also be steady. The same two objects must give the same answer every time you ask, and the answer must not depend on which one you call it on.

Dataclasses do this for you

A dataclass is a short way to write a class that only holds data. The dataclass decorator writes __init__, __repr__ and __eq__ from the fields you list. With frozen=True, the object cannot change after it is made, and the decorator also writes __hash__. The next program does the same job as the Point class above in a few lines.

dataclass lookup: home
repr: Cell(row=1, col=2)

A frozen dataclass is the simplest choice for a key that holds plain values. It has one limit that surprises people, shown in the next program. The generated __hash__ hashes the tuple of fields, so a field that holds a list makes the whole object unhashable.

TypeError: unhashable type: 'list'
tuple box lookup: first

The fix is to store a tuple in the field. A tuple of the same items is equal to another tuple with the same items, and it has a hash value. A list holds the same items but cannot be hashed, because it can change.

When the rules break

The three rules are not checked by Python before the program runs. A class can break them, and some mistakes show up as loud errors while others quietly give wrong answers. These cases show both kinds.

eq without hash

A class that defines __eq__ and not __hash__ has its __hash__ set to None by Python. Such a class is unhashable, and a dict or a set refuses it with an error at the moment you use it as a key.

TypeError: cannot use 'EqOnly' as a dict key (unhashable type: 'EqOnly')

In Java the same mistake compiles, and the map quietly gives wrong answers. Python's error is loud, which is better, because the bug shows up on the first run. The fix is the one from the earlier section: define __hash__, or use a frozen dataclass.

Changing a key after it is stored

This version of Tag has a name attribute that can change. Its __eq__ and __hash__ both read name.

get(t) after changing the key: None
get(new alpha): None
get(new beta): None
size: 1
stored key name now: beta

The entry was filed under the hash value of "alpha". After the rename, every lookup computes the hash value of "beta" or "alpha", and each one points to a slot that does not hold the entry. The entry is still in the dict, as the size and the loop show. It just cannot be found by either name. The dict gave no error. This is the reason to make key fields read-only, which a frozen dataclass does for you.

Correct but slow

A class can have a poor __hash__ and still give correct answers. The next example returns only x from __hash__.

size: 4
same hash for (7,0) and (7,3): True
get (7,3): 3

All four points have the same hash value, so they all go to one slot. __eq__ still tells them apart, so the answers are correct. The cost is speed. A lookup has to compare the key with every key that shares the slot. With a few keys nobody notices. With tens of thousands of keys that all share one hash value, each lookup can become a long scan. A good __hash__ uses every field that __eq__ compares.

Pair keys: tuples

A pair of numbers is the natural key for a grid cell or a coordinate. In Python you do not need to write a hash function for it. A tuple of two numbers is hashable, and its hash value already mixes the two numbers in order. The next program uses tuples as keys, shows that order matters, and shows that the tuple hash keeps (3, 3) and (0, 0) apart.

tuple keys: 5 7 2
order matters: True
tuple hashes differ for (3,3) and (0,0): True

The tuple hash is designed for this job. Java and C++ need a helper for the same purpose. C++ has no built-in hash for std::pair, and a naive helper can give poor results in any language. The next program shows the naive mistake in Python, so you can recognise it in code written for other languages.

A common naive hash for a pair combines the two parts with the exclusive-or operator ^. That operator gives 0 when both inputs are equal. So (3, 3) and (0, 0) both get 0 from the naive combination. The dict would still answer correctly, because == on the pairs decides equality. But the two keys would share a slot, so the dict would do more work.

naive hash of (3,3): 0
naive hash of (0,0): 0
naive hashes equal: True
tuple hashes equal: False

The naive combination makes the two pairs collide. The tuple hash does not. This is why you should use a tuple as the key, and not build your own combination.

Packing two numbers into one integer is another approach. It is common in languages with fixed-size integers, where the two numbers fit into one 64-bit value. Python integers have no fixed size, so the packing is a choice, not a need. If you do pack, shift one number left with << (this moves its bits up) and mask the other with & (this keeps only the bits in the mask), so that a negative number does not fill the other part with ones.

pack(1,2): 4294967298 pack(2,1): 8589934593
pack(-1,3): -4294967293
three different keys: 3

The mask 0xFFFFFFFF keeps only the low 32 bits of y. Without it, a negative y would set bits in the upper part and blur the result. Packing works only when both values fit in 32 bits, which is a limit you must check yourself. For most code a tuple is clearer, and it has no limit.

Common mistakes

Defining eq with no check on the type

A method that reads other.x without checking other breaks when someone compares the object with a different type. The error comes from the comparison, not from the dict, so it can appear far from the real cause.

class LoosePoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
 
 
print(LoosePoint(1, 2) == "oops")

Traceback (most recent call last):
  ...
AttributeError: 'str' object has no attribute 'x'

The fix is to return False for other types. The isinstance check in the Point example does this. Returning NotImplemented is the more formal choice, and Python then tries the other side of the comparison first.

Forgetting hash when you define eq

The error is the one shown in the section above: TypeError: cannot use 'EqOnly' as a dict key (unhashable type: 'EqOnly'). The fix is to define both methods, or to use a frozen dataclass, which writes both for you.

A mutable dataclass as a key

A mutable object is one whose fields can change. A plain @dataclass writes __eq__ but sets __hash__ to None, because a mutable class should not be a key. The error appears when you use it as a key:

from dataclasses import dataclass
 
 
@dataclass
class Seat:
    row: int
    number: int
 
 
booked = {Seat(3, 14): "Ravi"}

TypeError: cannot use 'Seat' as a dict key (unhashable type: 'Seat')

Add frozen=True if the seat never changes after it is made. If it must change, keep it out of the dict, or use a tuple such as (3, 14) as the key.

A list inside a key

A list cannot be a key, and a set cannot hold one either. The error names the type:

counts = {[1, 2]: 5}

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Use a tuple, such as (1, 2). A tuple of hashable items is hashable, and an equal tuple finds the same entry.

Expecting a naive hash to be enough

A hash that uses fewer fields than __eq__ is correct but can be slow, as the SlowPoint example shows. A hash that uses more fields than __eq__, or an unrelated field, breaks rule 3 and gives wrong answers. Write __hash__ from the same fields as __eq__, or let a dataclass do it.

Practice

Exercise 1. Use a frozen dataclass Cell(row, col) in a set. Start at row 0, column 0, and add the start cell to the set. Then walk the moves RRDDLU, where R adds 1 to the column, L subtracts 1 from the column, D adds 1 to the row and U subtracts 1 from the row. Add each new cell to the set. Print how many distinct cells you visited, and print whether the set contains Cell(1, 1).

Show the answer

The set holds 7 distinct cells: (0,0), (0,1), (0,2), (1,2), (2,2), (2,1) and (1,1). The check for Cell(1, 1) prints True.

distinct cells: 7
visited (1,1): True

Exercise 2. A class Key has two attributes, name and id. Its __eq__ compares both attributes. Its __hash__ returns hash(self.name) and ignores id. After m[Key("a", 1)] = "x", will m.get(Key("a", 1)) find the value?

Show the answer

Yes. Two equal keys have the same name, so they get the same hash value. Ignoring id in __hash__ is allowed, because the rule only forbids using a field that __eq__ ignores. The cost is that keys with the same name share a slot.

Exercise 3. A class Seat has row and number. Its __eq__ compares only row. Its __hash__ returns hash(self.row) + self.number. Find the rule this breaks, and say what can go wrong in a set of seats.

Show the answer

Rule 3 is broken. __hash__ uses number, which __eq__ ignores. Two seats in the same row are equal, but their number values can differ, so they can get different hash values. The set may then keep both, and it can hold two seats that are equal to each other. The next program shows the set holding two equal seats. The fix is to make __eq__ compare number too, or to remove number from __hash__. Pick the first fix if seats with the same row and different numbers are truly different.

size: 2
equal seats: True
same hash value: False

Exercise 4. Use a dict with tuple keys to store the value 4 under (10000000000, 2) and the value 8 under (2, 10000000000). Print both values and the size of the dict.

Show the answer

The program prints 4 8 2. The two keys differ, so both are stored. Python integers have no size limit, so the large number needs no special type.

4 8 2

Exercise 5. A dict uses a list [1, 2] as a key. What happens, and what is the fix?

Show the answer

Python raises TypeError: cannot use 'list' as a dict key (unhashable type: 'list') when the dict is built. The fix is a tuple, (1, 2). A tuple cannot change, so its hash value stays valid for the life of the key.

Summary

• A dict uses the hash value to pick a slot and == to confirm the key. Both must agree for a custom key to work.
• Define __eq__ and __hash__ together, and check the type of other inside __eq__. Use a frozen dataclass when the key only holds plain values.
• Equal objects must have equal hash values, and __hash__ must use only fields that __eq__ also compares.
• Keys must not change while they are stored. Make key fields read-only, and use tuples instead of lists.
• For a pair of numbers, use a tuple. A tuple's hash already mixes the two values in order, so no custom combination is needed.