vizlearn

How does a Python dict work?

Interview QuestionsBy Updated

A hash table. The key's hash picks a slot, so a lookup computes an address rather than searching — which is why the size of the dictionary does not appear in the cost. Collisions are resolved by probing, and the table resizes and rehashes everything once it gets too full.

Overview

Computing an address instead of searching

Two steps: hash the key to a number, then fold that number into a slot index. The lookup goes straight to that slot and compares keys there. Neither step depends on how many entries the dictionary holds, which is the entire O(1) claim.

The comparison at the end is not optional. Two different keys can share a slot, so the answer is only correct because the key itself is checked — see hash tables for the machinery in full.

Dicts, sets & hashingConceptualMedium

Step through it

What to watch

  • The slot is computed, never searched for.
  • A collision does not break anything — it costs an extra probe.
  • A resize invalidates every slot, because the index is hash % size.

Say this out loud

"Hash table. hash(key) picks a slot, so lookup is a computation, not a search - O(1) average. Collisions probe to another slot, and it resizes and rehashes when the load factor gets too high. Worst case is O(n) if everything collides."

How does a Python dict work?

How is a dictionary implemented, and why is lookup O(1)?

Collisions and the load factor

When two keys want the same slot, CPython probes for another one using a sequence derived from the hash. That costs extra comparisons, and the fuller the table the longer the probe sequences get.

So the table grows before that becomes a problem — past roughly two-thirds occupancy it allocates a bigger one and reinserts everything. A resize is O(n) and every key's slot changes, because the index is hash % size and size just moved. Amortised over the insertions that caused it, insertion is still O(1).

When O(1) is not true

If every key hashes to the same slot, every operation degrades to a linear scan. That is not hypothetical: it was a real denial-of-service attack, where an attacker sent form fields chosen to collide. Python's answer is hash randomisation — string hashes are salted per process, so an attacker cannot precompute a colliding set.

That is also why dictionary iteration order must never be assumed to be hash order, and why hash('x') differs between runs.

Run it in Python

A miniature hash table built from a list of buckets so the slot arithmetic is visible, then the same keys with a deliberately terrible hash so you can watch O(1) become O(n).

how_dicts_work.pyPython 3
Output
How the code works
  1. self.hash_fn(key) % self.slotsTwo separate jobs. The hash turns a key into a number; the modulo folds it into a valid index. Change the number of slots and every index changes.
  2. for k, v in self.buckets[...]The comparison that makes the answer correct rather than probable. Two keys can share a slot, so the key itself has to be checked.
  3. if self.count / self.slots > 0.66:The load factor. Probe sequences lengthen sharply as a table fills, so it grows before that happens rather than after.
  4. hash_fn=lambda k: 1Every key in one slot. The structure still works perfectly and every guarantee has evaporated — which is the point worth making about hash tables in general.
Change one thing
  • Use hash_fn=len. Words of equal length collide, which is a far more realistic bad hash than the constant one.
  • Print the buckets, then run the program again. The layout moves, because string hashing is salted per process.
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. Dictionary lookup is O(1) because:
  2. Why does a resize have to rehash every key?
  3. Python randomises string hashes per process in order to:





 Cheat sheet
How does a Python dict work?
A hash table. The key's hash picks a slot, so a lookup computes an address rather than searching — which is why the size of the dictionary does not appear in the cost. Collisions are resolved by probing, and the table resizes and rehashes everything once it gets too full.
INTERVIEW · vizlearn.in/interview/how-does-a-python-dict-work.html
More in Interview
InterviewWhy must dictionary keys be hashable?InterviewCount things with a dictionaryInterviewWhat is the complexity of this code?InterviewWhy are Python strings immutable?
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