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).
The same structure with a hash function that never spreads keys out turns every lookup into a linear scan.
Python also salts string hashes per process, which is a different but related property worth seeing right.
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.
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.
| 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; 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.