Hashing your own keys

Numbers, strings and tuples work as dict keys and set items. Lists don't:

places = {}
places[[2, 3]] = "home"

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    places[[2, 3]] = "home"
    ~~~~~~^^^^^^^^
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Why a list can't be a key

A table finds a key by its hash, worked out when the key goes in. A list can change after that: append to it, and its hash, if it had one, would change too. Its pair would then sit in the bucket of the old hash, where no lookup ever looks again. So among Python's own types, only those whose values can't change, the immutable ones, are hashable: numbers, strings and tuples. A tuple can't change, so (2, 3) works as a key, and the usual way to use a list as a key is to make a tuple of it first: places[tuple(position)] = "home". A tuple is hashable only if everything in it is: ([2], 3) isn't.

Keys of your own

Objects of your own classes can be keys, but by default both == and the hash go by identity: two Point(1, 2) objects are two different keys. Once a class has __eq__, Python takes its default hash away, and putting a point in a set stops with TypeError: cannot use 'Point' as a set element (unhashable type: 'Point'). You write __hash__ too, and the two methods must agree:

Objects that are equal must have equal hashes. A table looks for a key only in the bucket of its hash, so if two equal points had different hashes, a lookup for one would never find the other. Objects that aren't equal may share a hash; that's just a collision.

The easy way to keep the rule is to hash a tuple of exactly the fields that __eq__ compares. __hash__ returns a whole number, and the table works out the bucket from it:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

    def __repr__(self):
        return f"Point({self.x}, {self.y})"


p = Point(1, 2)
visited = {p}
visited.add(Point(1, 2))
print(len(visited), Point(1, 2) in visited, Point(2, 1) in visited)

p.x = 5
print(visited)
print(p in visited, Point(1, 2) in visited)

1 True False
{Point(5, 2)}
False False

The second Point(1, 2) is equal to the first and has the same hash, so the set keeps one point. Then the program changes the point while it's in the set. The set still holds it, as the print shows, but nothing finds it any more: p in visited looks in the bucket of the new hash, and Point(1, 2) finds the right bucket but no equal point in it. So a key must not change while it's in a table: hash only fields that never change after __init__, or use tuples.

A legal hash that's terrible

return 0 keeps the rule too: equal objects get equal hashes. But then every object collides with every other, and the table is one long chain. This class counts how often the set calls its __eq__:

class Ticket:
    comparisons = 0

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

    def __eq__(self, other):
        Ticket.comparisons += 1
        return self.number == other.number

    def __hash__(self):
        return 0


tickets = set()
for i in range(1000):
    tickets.add(Ticket(i))
print(len(tickets), Ticket.comparisons)

1000 613645

Each new ticket is compared with the tickets already there, so building a set of n tickets is O(n²), and each lookup O(n). With return hash(self.number) instead, the program prints 0 comparisons: the set calls __eq__ only for keys whose hashes are equal, and these numbers all have different hashes.