Hashing and mutability: why lists can’t be dict keys

Looking a key up in a dict takes about the same time whether it holds ten entries or ten million. The trick is the hash: a number worked out from the key's value. Python uses it to jump straight to the place in the table where that key must be, then uses == to make sure it found the right one.

print(hash(7))                              # 7: small ints hash to themselves
print(hash((1, "a")) == hash((1, "a")))     # True: equal values, equal hashes
print(hash("tea"))   # a big number; for text it usually changes each time Python starts

The rule that makes it work

The table only works if two things stay true:

1. 1objects that are equal have the same hash;
2. 2a key's hash never changes while it's in a dict or set.

A list could change after you used it as a key, and then its hash would point to the wrong place. So Python refuses: lists, dicts and sets are unhashable.

spots = {}
spots[["A", 1]] = "taken"

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

(Python 3.14 added the first half of that message. Older versions say just unhashable type: 'list'.)

Immutable values are hashable: numbers, strings, None, and tuples, as long as everything inside them is hashable too. So when you need a compound key, use a tuple: spots[("A", 1)] = "taken" works.

Your own classes

A class you write is hashable from the start: by default, objects are equal only to themselves, and the hash comes from the identity. But the moment you define __eq__ to compare values, Python sets __hash__ to None, because the old identity-based hash would break rule 1 (two equal objects, two different hashes). If you want your objects as keys, write a __hash__ built from the same fields __eq__ compares. Hashing a tuple of them is the usual way.

See rule 2 broken

Here's a class that follows rule 1, but whose objects can still change. Watch a key get lost inside a set:

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

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

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


mine = Locker(12)
in_use = {mine}
print(mine in in_use)          # True
mine.number = 7                # change the key after it went in
print(mine in in_use)          # False: Python looks where 7 would be
print(Locker(12) in in_use)    # False: what's stored there is now 7
print(len(in_use))             # 1: still in there, just lost

That's why hashable objects should also be immutable. The next lesson shows the easy way to get both.

More in the Python docs: hashable, object.__hash__ and dictionaries.