dictPython's most-used container and the one that makes x in d and
d[key] feel instant. It's a hash map — Java's HashMap — and
understanding the one trick behind it (hashing) explains its speed, its rules about keys, and a
surprising amount of how Python itself is built.
You could store key→value pairs in a list and, to find a key, scan from the front comparing each one. That's O(n): with a million entries, a million comparisons. A dict avoids the scan with a single idea: run the key through a hash function — a deterministic function that turns the key into an integer — and use that integer to jump directly to the slot ("bucket") where the value lives. No scanning; you compute the address. That's why lookup is roughly O(1), independent of how many entries there are.
The flow for both storing and finding is identical:
key → hash(key) → bucket index → value. Add a few entries and
watch each key land in a bucket. (We use a tiny 8-bucket table and a toy hash so collisions are visible — a
real dict has many more buckets and grows as it fills.)
For the trick to work, a key must (1) produce the same hash every time, and (2) compare equal to
itself reliably. Mutable objects break promise (1): if you used a list as a key and then
appended to it, its hash would change and the dict could never find it again. So Python forbids it — keys
must be immutable / hashable: numbers, strings, and tuples work; lists, sets, and dicts don't. This
is the exact same constraint that lets something be a set member, and
it's why immutability matters so much in Python.
Dicts aren't just a data structure you reach for — they're load-bearing inside Python. An
object's attributes live in a dict (obj.__dict__); a module's globals are a dict; keyword
arguments arrive as a dict. So fluency here pays off far beyond "mapping words to counts." Common idioms:
From Python 3.7 on, a dict also preserves insertion order, so iterating gives keys back in the order you added them — handy, though you still shouldn't rely on a dict for sorted order.
d[key] and
key in d are ~O(1), not an O(n) scan. Keys must be hashable (immutable) — strings,
numbers, tuples yes; lists no. Two keys can collide into one bucket; the dict resolves it. Dicts
preserve insertion order and quietly power objects, modules, and **kwargs.Visual companions: step through dict operations in Python Tutor, or watch hashing & collisions animate at VisuAlgo — Hash Table.