Dictionaries & Hash Tables
Python's dict is a hash table offering average O(1) lookup, insertion-ordered since 3.7 — the workhorse behind objects, kwargs and namespaces.
Learning objectives
- › Explain how hashing gives average O(1) lookup
- › State why keys must be hashable and what that implies
- › Describe insertion-order guarantees since Python 3.7
- › Use defaultdict, Counter and dict comprehensions idiomatically
Prerequisites
Version notes
- · Insertion order is a language guarantee since 3.7 (an implementation detail in 3.6).
- · The compact dict layout (3.6+) cut dict memory by ~20–25%.
Simple explanation
What it is. A dictionary maps hashable keys to values using a hash table. Looking up a key hashes it to a slot, so on average you find (or insert) a value in constant time regardless of size.
Why it exists. Associative lookup is everywhere — object attributes, function keyword arguments, module namespaces and JSON-shaped data are all dicts under the hood. A fast, general mapping is foundational.
The problem it solves. It replaces slow linear scans with near-instant keyed access, and its ordering guarantee makes iteration predictable for serialization and caching.
How it works. The key's __hash__ picks a bucket; __eq__ resolves collisions when two keys land in the same bucket. Mutable objects can't be keys because their hash could change and lose the value. The table grows and rehashes as it fills to keep collisions rare.
Analogy: A coat-check: your ticket number (hash) tells the attendant exactly which hook to go to, instead of searching every hook one by one.
Common misconceptions
- "Dicts are unordered." — Not since 3.7; they preserve insertion order.
- "Any object can be a key." — Only hashable (usually immutable) objects can.
- "Lookup is always O(1)." — It's O(1) *average*; pathological hash collisions degrade it, and hashing itself costs time.
Common alternatives
- list of pairs (only for tiny, order-critical data)
- collections.OrderedDict for move_to_end semantics
- a sorted structure when you need range queries
Interactive visualization
1d = {}2d["apple"] = 1 # hash("apple") -> a slot3d["banana"] = 2 # hash("banana") -> a slot4print(d["apple"]) # hash again -> O(1) lookup
Heap / objects
8 slots (all empty)
An empty hash table
A dict is a hash table: a sparse array of slots. A small dict starts with 8 slots, mostly empty.
Code examples
Behind the scenes
- ▸CPython uses open addressing with perturbation probing to resolve collisions.
- ▸The compact layout stores entries in a dense insertion-ordered array with a separate sparse index array.
- ▸The table resizes (typically to keep it ~2/3 full) and rehashes existing keys when it grows.
- ▸hash(x) for the same value can differ per process for str/bytes due to hash randomization (PYTHONHASHSEED).
Interview insights
Key definitions
- · Hash table: a structure mapping keys to slots via a hash function for average O(1) access.
- · Hashable: an object with a stable __hash__ and meaningful __eq__ (typically immutable).
How does a dict achieve O(1) lookup, and why must keys be hashable?
Concise answer: It hashes the key to a bucket index for direct access, using equality to resolve collisions. Keys must be hashable so their bucket is stable; mutable keys could change hash and be lost.
Detailed answer: hash(key) maps to a slot; if occupied by a different key (collision), probing continues until the key or an empty slot is found. Average cost is O(1) because collisions are rare when the table stays sparse. If a key's hash changed after insertion, the dict would look in the wrong bucket — hence the immutability/hashability requirement.
Common mistake: Claiming worst-case is also O(1); heavy collisions degrade it.
Follow-ups:
- · Are dicts ordered? Since when?
- · What is hash randomization?
Knowledge check
Which can be a dict key?
Since which version is dict insertion order guaranteed by the language?
Score: 0/2