Run it
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).
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 everything in one contiguous array, which is better for CPU caches.
CPython's probe sequence is deliberately 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 — individual 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 effectively lost.
So Python requires keys to be hashable, and mutable built-in types deliberately are not.
The contract between hashing and equality has two rules:
Equal objects must have equal hashes. Otherwise 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, which 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, 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.
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.
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 introduced 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 consequences. 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 consequences:
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, which is a deliberate simplification and occasionally surprising.
| Operation | Average | Worst |
|---|
| Lookup | O(1) | O(n) |
| Insert | O(1) amortised | O(n) on resize |
| Delete | O(1) | O(n) |
| Iteration | O(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; heavy deletion therefore leaves the table sparse until it is resized. And memory use is higher than a list of the same values, which is the price of the lookup speed.
Questions people ask
Why is dictionary lookup O(1)? The hash computes the slot directly, so the work does not depend on the number of keys. The average chain length is bounded by keeping the table two thirds empty.
Are dictionaries ordered? Insertion order is guaranteed since 3.7. That is not sorted order.
Why can a list not be a key? Mutating it would change its hash and orphan the entry.
Chaining or open addressing? CPython uses open addressing with a scattering probe sequence; Java uses chaining, upgrading long chains to trees.
What is the load factor? The fill ratio that triggers a resize — about 2/3 in CPython.
Why do string hashes change between runs? Deliberate per-process randomisation, to prevent collision-based denial-of-service attacks.
Recap in one screen
- Hash the key, index into a slot array, compare — one calculation and a memory access, so O(1) on average.
- Collisions are inevitable and are resolved by probing; the table resizes at about two thirds full.
- Keys must be immutable, because a changing hash would orphan the entry, and
__eq__ and __hash__ must agree. - The compact layout stores entries contiguously in insertion order, which gives both the ordering guarantee and lower memory use.
- String hashes are randomised per process to prevent deliberate-collision attacks.