54The hash map — a value by its key, instantly

In Chapter 53 we gave the list two fast ends and called it a deque. But every structure so far, the deque included, still reaches a thing by its position: you either know the index or you walk to it. Here we break that pattern. A hash map — Python spells it dict — answers "what's the value for this key?" without touching any other entry. Not by walking, and not by binary search, but by computing the address straight from the key and jumping there in a single step. Here's the plan. We'll watch a key turn itself into a bucket number, see what happens when two keys want the same slot, learn why the table is kept deliberately two-thirds empty, weigh why it's the heaviest structure per item you'll meet, and find out why a key has to be frozen solid. All the way through we keep asking the one question the trick hangs on: how can you find one entry among millions without ever searching for it? By the end you'll read d[key] and see the hash, the bucket, and the single jump — and you'll know on sight when a problem is really a hash-map problem.

01The address is hidden inside the key

Let's start with the limit every structure so far has quietly shared. A list lands on a[i] with one multiply-and-add, because its cells are contiguous in memory (Volume 1, where we first laid an array down). But that only works when you already know the index. So watch what happens the moment your key isn't a number — a song title, a username, an IP address, a label rather than a position. Searching a list for it is an O(n) walk. Keeping it sorted and binary-searching drops that to O(log n) (Volume 3). The hash map does the thing that sounds impossible: it reaches the value in O(1) average. That's one jump, whether two entries sit inside or two billion.

The trick is a function called hash. Feed it any hashable object and it hands back a fixed-size integer — a scramble of the key's contents. Take that integer mod the table size and you have an index into a plain array of slots called buckets. So the key computes its own address: bucket = hash(key) % N. To store, you scramble the key to a bucket and drop the value there. To look up, you scramble the same key to the same bucket and read the value back. Both touch exactly one slot. That's the whole idea, and everything else in this chapter is us defending it.

Here is the derivation the O(1) hangs on. Computing hash(key) depends on the key's own size, not on how many entries the table holds. The % N is one integer op. The array is contiguous, so "jump to bucket b" is one base + b × slot address computation — the exact primitive from Volume 1's list. Add those up and the work to find any entry is independent of n. That is the definition of O(1). The list had to walk n slots, and the sorted array bisected to log n. The hash map skips the search entirely, because the key already knows where it lives.

>>> hash(42)          # small ints hash to themselves
42
>>> hash(42) % 8      # ... so the bucket is just the low bits
2
>>> d = {"Levels": 84, "Strobe": 631}
>>> d["Levels"]       # hash("Levels") % N -> one jump -> 84
84

I ran it. hash(42) is 42 (small integers hash to themselves), so hash(42) % 8 is 2 — bucket 2, computed straight from the key. Notice what d["Levels"] doesn't do: it never looks at the "Strobe" entry at all. It hashes "Levels", takes the mod, jumps, and reads. Two entries or two billion, the lookup does the same amount of work.

One jump — as long as no two keys ever want the same bucket. But with 8 buckets and a 9th key, two must collide. What happens then? →

02When two keys want one bucket

Collisions are not a bug; they are arithmetic. You are squeezing a giant space of possible keys through % N into N slots. So the moment you have more than N keys, two of them share a bucket by the pigeonhole principle — and long before that, birthday-style coincidences make near-collisions common. A hash map is really two ideas joined together: a function that scatters keys evenly, and a plan for when the scatter lands two keys on the same slot.

There are two classic plans. Chaining: each bucket holds a little linked list, and colliding keys hang off the same bucket. Open addressing: keep everything in the one flat array, and if your bucket is taken, probe — try another slot by a fixed rule until you find a free one. CPython's dict uses open addressing, because a flat array streams through cache far better than chasing per-bucket linked-list nodes across the heap (Volume 3, where pointer-chasing stalls while contiguous memory runs fast). The figure below shows the simplest probe, which is to walk to the next slot. But see the deeper cut: real CPython uses a perturbed sequence so collisions don't clump.

Build the intuition by driving it. In the widget, pick a key and watch it compute hash % 8 and light up its home bucket. Insert it, and watch a collision probe forward to the next free slot.

Probing stays cheap only while there's plenty of free space to probe into. Let the table fill up and every insert turns into a long hunt. So the map watches how full it is — and acts. →

03Two-thirds full, then grow

The number that governs a hash map's health is the load factor: entries divided by buckets. Empty is 0, and half full is 0.5. As it climbs toward 1.0, free slots vanish, probe chains lengthen, and the O(1) decays into an O(n) scan. So the map never lets it get close. CPython resizes the moment the table would cross two-thirds full. It grows the bucket array (doubling it) and rehashes every existing key into the bigger table, because each key's bucket is hash % N and N just changed.

You can watch it happen with sys.getsizeof. I inserted integers one at a time and printed only when the table's byte size jumped:

import sys
d = {}
prev = sys.getsizeof(d)
for i in range(1, 130):
    d[i] = i
    s = sys.getsizeof(d)
    if s != prev:                 # only print the resize moments
        print(i, prev, "->", s)
        prev = s
# 1   64 -> 224     (first key: an 8-bucket table appears)
# 6   224 -> 352    (6th key crosses 2/3 of 8  -> grow to 16)
# 11  352 -> 632    (11th crosses 2/3 of 16    -> grow to 32)
# 22  632 -> 1168   (22nd -> 64)   43  1168 -> 2264  (-> 128)   86  2264 -> 4688  (-> 256)

Read the resize points: 6, 11, 22, 43, 86. Those are exactly two-thirds of 8, 16, 32, 64, 128 — the table doubles every time it crosses the line. An empty dict is a bare 64-byte header with no bucket array at all. The first key creates an 8-slot table, jumping the size to 224 bytes. From there, each resize copies every key into a fresh, larger, mostly-empty array. That copy is O(n), but it happens rarely and the table doubles, so the cost amortizes to O(1) per insert (the same amortized bookkeeping as the list's overallocation, back in Volume 3). You pay a big bill occasionally to keep every other insert instant.

Doubling to stay two-thirds empty is why lookups fly — and also why a hash map is the heaviest structure you'll carry. Let's weigh it. →

04The heaviest structure per item

Every deal with memory has a price, and the hash map's is space. Look back at the layout. A big fraction of the buckets are deliberately empty — that's the load factor — and each occupied bucket doesn't just hold a value. It holds the hash, and a reference to the key, and a reference to the value. A list stores one 8-byte reference per element and nothing else. The dict stores far more, and keeps spare slots on top. Here's the same data both ways, measured:

import sys
keys = range(1000)
d = {k: k for k in keys}
L = list(keys)
print(sys.getsizeof(d))   # 36952  -> ~37 bytes per slot
print(sys.getsizeof(L))   # 8056   -> ~8  bytes per slot

big = {i: i for i in range(1_000_000)}
print(sys.getsizeof(big)) # 41943128  -> ~41.9 bytes per entry (~41.9 MB)

The list of 1000 is 8,056 bytes — about 8 per element, one reference apiece. The dict is 36,952 bytes, roughly 37 per slot. That's four to five times heavier, and it's just the table, before counting the key and value objects it points to. Scale up and it holds: a million-entry dict weighs ~41.9 MB of table alone (~41.9 bytes/entry). That is the space-for-speed bargain stated in bytes. You buy the single-jump lookup by keeping the array sparse and paying for two references and a cached hash per entry.

Sparse, reference-heavy, self-resizing — and it all rests on one quiet assumption about the key: that its hash never changes. Break that and the value vanishes. →

05Why a key must be frozen

A hash map finds a key by recomputing hash(key) and going to that bucket. That only works if the key hashes to the same bucket every time. So the key must be hashable, which in practice means immutable: its contents, and therefore its hash, can never change while it's in the map. Strings, numbers, and tuples of immutables qualify. Lists and dicts do not, and Python refuses them outright:

>>> {[1, 2]: "x"}
TypeError: unhashable type: 'list'
>>> {(1, 2): "point"}[(1, 2)]      # a tuple is frozen -> fine
'point'

Why the hard ban? Picture what a mutable key would do. Suppose the map let you use a mutable object whose hash tracked its contents. You store value under it, landing in bucket 4. Then you mutate the key, and now it hashes to bucket 7. Ask the map for it: lookup goes to bucket 7, finds nothing, and reports the key missing — while the value sits orphaned in bucket 4, unreachable. I built exactly that trap:

class Bad:
    def __init__(self, v): self.v = v
    def __hash__(self): return hash(self.v)   # hash tracks a mutable field
    def __eq__(self, o):  return self.v == o.v

k = Bad(1)
store = {k: "found me"}
print(store.get(k))        # 'found me'   -> hashes to its bucket, found
k.v = 999                  # mutate the key: its hash just changed
print(store.get(k))        # None         -> now hashes elsewhere, lost
print("found me" in store.values())   # True -> still physically in the table

The output was 'found me', then None, then True. The value never left the table; the key just stopped pointing at the right bucket. That is why immutability isn't a style rule here, it's a correctness requirement. Freezing the key is the price of computing its address. (This is the Volume 1 callback made concrete: hashability is exactly the contract a key signs.)

$ python -c "print(hash('secret'))"
-7922894392216367691
$ python -c "print(hash('secret'))"
7804674963121063573        # different seed each process -> different hash
$ python -c "print(hash(42))"
42                          # ints aren't randomized: hash(n) stays n

I ran hash('secret') in three fresh interpreters and got three unrelated numbers, while hash(42) came back 42 every time. String hashes are salted per process (that's PYTHONHASHSEED at work). Integer hashes aren't, because they're not the flooding target. Same key, same run gives the same bucket. A different run may give a different bucket. That's also why you should never persist a Python hash to disk and expect it to match next launch.

Frozen keys, defended averages, a table two-thirds empty — add it up and you have the workhorse of modern computing. Where does it actually run? Almost everywhere, including inside Python itself. →

06Where you meet this — everywhere, including inside Python

The access pattern the hash map owns is "reach a thing by its label", and once you see it, you see it constantly. Every dict you write, obviously. But also: database indexes (a hash index turns a WHERE-clause value straight into a row location, with no table scan); Redis and memcached, whole databases that are essentially one giant hash map living in RAM, serving billions of lookups a second; deduplication (drop everything into a set, and collisions reveal the duplicates); a compiler's symbol table, mapping every variable name to its type and address as it parses your code; and memoization/caching — @lru_cache is a dict keyed by your function's arguments.

A set is the same machinery with the values thrown away: a hash table that stores only keys, answering "is x in here?" in O(1). I measured a membership test on a million-element set at about 38 nanoseconds. The list's worst-case scan of the same size I clocked at roughly 6.4 milliseconds, over a hundred-thousand times slower. When your question is "have I seen this before?" or "is this in the allowed set?", that gap is the whole reason sets exist.

Because a hash map scatters keys to random buckets, it destroys one thing utterly: order. Ask it for "the smallest key," or "every key between 10 and 20," and it has no answer but to scan everything. The structures ahead keep order on purpose. But first, the next chapter leaves the world of one-dimensional rows entirely — it arranges data in a grid, rows and columns, and asks a question that decides how fast every image filter and neural network runs: when you store a 2-D table in 1-D memory, which way do you lay it down? →