vizlearn

Why must dictionary keys be hashable?

Interview QuestionsBy Updated

Because the entry is stored in a slot chosen from the key's hash. If the key could change afterwards, its hash would change, the lookup would go to a different slot, and the entry would be unreachable. So keys must be immutable — tuples and strings qualify, lists and dicts do not.

Overview

The invariant being protected

Equal objects must have equal hashes, and an object's hash must not change while it is in use as a key. Both follow from how the table works: the hash is the address, so a moving hash is a moving address.

Python enforces this by making mutable built-ins unhashable. list, dict and set all set __hash__ = None, which is why the error is unhashable type rather than something about dictionaries.

Dicts, sets & hashingConceptualMedium

Step through it

What to watch

  • The rule follows from the storage, not from taste.
  • Mutating a key would leave the entry in a slot nothing looks at.
  • A tuple containing a list is also unhashable — it goes all the way down.

Say this out loud

"The key's hash decides where the entry lives. If the key could mutate, the hash would change and you could never find the entry again - so keys have to be immutable. A tuple works; a list doesn't."

Why must dictionary keys be hashable?

Why can a tuple be a dictionary key but a list cannot?

It goes all the way down

A tuple is hashable only if everything in it is. (1, 2) is a fine key; (1, [2]) is not, because the tuple's hash is derived from its contents and one of them can change.

frozenset is the immutable set, and it is hashable for the same reason. set is not, which is why you cannot have a set of sets without it.

Custom objects

By default a custom object hashes by identity, so two equal-looking instances are different keys. Define __eq__ and Python sets __hash__ to None — because you have redefined equality and the default hash no longer agrees with it.

To make it usable as a key, define __hash__ too, over the same fields __eq__ uses, and do not mutate those fields afterwards. @dataclass(frozen=True) does all of this correctly for you.

Run it in Python

What is and is not hashable, then a class that breaks the contract on purpose — mutating a key after insertion and losing the entry, exactly as the visualisation describes.

hashable.pyPython 3
Output
How the code works
  1. hash((1, [2]))Fails, because a tuple's hash is computed from its contents. Immutability has to hold all the way down, not just at the top level.
  2. key.tag = "b"The contract broken deliberately. The entry stays in the slot chosen by the old hash while lookups go to the new one, so it is lost while still occupying memory.
  3. list(d.items())The entry is still there and still iterable — only lookup by key is broken. That is what makes this class of bug so hard to diagnose.
  4. @dataclass(frozen=True)Generates __eq__ and __hash__ over the same fields and blocks assignment. It is the correct way to make a value object usable as a key.
Change one thing
  • Define __eq__ on a class without __hash__ and try to use it as a key. Python sets the hash to None for you — deliberately.
  • Use a plain @dataclass instead of a frozen one. It is unhashable, for exactly the reason this page is about.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. A list cannot be a dictionary key because:
  2. Is (1, [2]) hashable?
  3. Defining __eq__ on a class without __hash__ makes instances:





 Cheat sheet
Why must dictionary keys be hashable?
Because the entry is stored in a slot chosen from the key's hash. If the key could change afterwards, its hash would change, the lookup would go to a different slot, and the entry would be unreachable. So keys must be immutable — tuples and strings qualify, lists and dicts do not.
INTERVIEW · vizlearn.in/interview/why-must-dict-keys-be-hashable.html
More in Interview
InterviewCount things with a dictionaryInterviewWhat is the complexity of this code?InterviewWhy are Python strings immutable?InterviewWhat does slicing a string cost?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact