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.

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."

Overview

Python dictionaries use a hash to locate candidate slots, then equality to confirm a key. Expected lookup is constant time, but collisions and resizing matter; hashes narrow the search and do not replace equality checks.

In this guide
  1. Run it
  2. Collisions and probing
  3. Why keys must be immutable
  4. Computing an address instead of searching
  5. Collisions and the load factor
  6. When O(1) is not true
  7. Insertion order, and the compact layout
  8. Hash randomisation
  9. Performance in practice
  10. Sources and next steps

Run it

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

1Python
Output

The same structure with a hash function that never spreads keys out turns every lookup into a linear scan.

2Python
Output

Python also salts string hashes per process, which is a different but related property worth seeing right.

3Python
Output

Collisions and probing

With a finite number of slots, collisions are inevitable. CPython uses open addressing: on a collision, probe for another slot using a sequence derived from the hash.

Chaining is the other classic approach — a linked list per slot — used by Java's HashMap. Open addressing keeps all of it in one contiguous array, which is better for CPU caches.

CPython's probe sequence is on purpose not a simple linear step; it uses the higher bits of the hash to scatter probes, which reduces clustering.

When the table becomes too full, collisions become frequent and lookups slow down. So the dictionary resizes: once it is about two thirds full, a larger table is allocated and every entry is rehashed into it.

That resize is O(n). Averaged over the insertions that fit in the new capacity, insertion is O(1) amortised. Single insertions can be expensive, the sequence is cheap. The same mechanism underlies list append.

Why keys must be immutable

A key's slot is determined by its hash. If the key changed after insertion, its hash would change. And the entry would sit in a slot the new hash does not point to. Unreachable, and in effect lost.

4Python
Output

So Python requires keys to be hashable, and mutable built-in types on purpose are not.

The contract between hashing and equality has two rules:

Equal objects must have equal hashes. If not two keys that compare equal land in different slots and both exist in the dictionary.

Unequal objects may share a hash. That is a collision, handled by probing.

For a custom class, define both together — and defining __eq__ without __hash__ makes the class unhashable in Python 3. This is a deliberate safeguard against violating the first rule.

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. This is the entire O(1) claim.

The check 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.

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 checks, 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 all of it. 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.

Insertion order, and the compact layout

Since Python 3.7, dictionaries preserve insertion order, and this is a language guarantee rather than an implementation accident. (It appeared as an implementation detail in 3.6.)

The mechanism is the compact dict layout added in 3.6, which splits the structure in two:

An indices array — the hash table proper, holding small integers pointing into the entries array.

An entries array — the actual (hash, key, value) triples, appended in insertion order.

That split has two results. Iteration walks the entries array, which is contiguous and in insertion order. Hence both the ordering guarantee and better cache behaviour. And the sparse array holds small indices rather than full triples. So memory use dropped by roughly 20–25% compared with the older layout.

It is a good example of an optimisation whose side effect became a language feature.

Hash randomisation

Python randomises the hashes of strings and bytes per process. Run the same script twice and hash("hello") differs.

The reason is security. Without randomisation, an attacker who knows the hash function can craft input where every key collides — turning O(1) lookups into O(n) and every dictionary operation into a denial of service. Web frameworks parsing untrusted keys were the vulnerable case.

Practical results:

Do not persist hash values or use them as stable identifiers across processes. Use a cryptographic hash if you need stability.

Set PYTHONHASHSEED=0 to disable it when you need reproducibility, in tests for instance.

Small integers are not randomised — hash(n) == n for small ints. This is a deliberate simplification and sometimes surprising.

Performance in practice

OperationAverageWorst
LookupO(1)O(n)
InsertO(1) amortisedO(n) on resize
DeleteO(1)O(n)
IterationO(n)O(n)

The worst cases require every key to collide, which needs either a bad custom __hash__ or adversarially chosen keys. And hash randomisation addresses the second.

Two practical notes. Deletion leaves a marker rather than a gap because removing an entry outright would break probe sequences that passed through it; repeated deletions can leave the table sparse until it is resized. And memory use is higher than a list of the same values. This is the price of the lookup speed.

For the underlying ideas, see hash tables, Python dictionaries and dictionary methods.

Sources and next steps

How the code works

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 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?

Look inside CPython's dict: a hash table with open addressing. See the probe sequence, the compact layout, and why average-case lookup costs O(1).

INTERVIEW · vizlearn.in/interview/how-does-a-python-dict-work.html

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.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.