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, deque included, still reaches a thing by its position. You either know the index or you walk to it. Here we break that spell. A hash map — Python spells it dict — answers "what's the value for this key?" without touching any other entry. It doesn't walk, and it doesn't binary-search. It works 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. We'll see what happens when two keys want the same slot. We'll learn why the table is kept deliberately two-thirds empty, why it's the heaviest structure per item you'll meet, and why a key has to be frozen solid. The whole 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 — 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. Now take that integer mod the table size. That gives you an index into a plain array of slots called buckets. So the key computes its own address: bucket = hash(key) % N. Store means "scramble to a bucket, drop the value there." Lookup means "scramble to the same bucket, read the value back." Both touch exactly one slot. That's the whole idea. Everything else in this chapter is us defending it.

You might reasonably ask why we bother hashing at all. Why not just use the key itself as the index? There are two reasons. First, most keys aren't numbers. A username or a song title has no natural row number, so there's nothing to index an array with until you turn it into one. Second, even when the key is a number, it can be astronomically large or sparse. A user ID like 900431772 would demand an array with nearly a billion slots to use it directly. Hashing solves both problems at once. It turns any key into an integer, and % N folds that integer down to fit the table you actually have.

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 them up: the work to find any entry is independent of n. That is the definition of O(1). The list had to walk n slots; 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", mods, jumps, reads. Two entries or two billion, the lookup does the same amount of work.

That 42 is a special case, and I'm flagging it so it doesn't quietly mislead you. Small integers hash to themselves, but a string gets genuinely scrambled. Feed hash a title like "Levels" and it returns a big, unpredictable integer with no visible relationship to the letters. The mod is what tames it. Say the scramble came out as 5381927. Then 5381927 % 8 is 7, because 8 divides evenly into 5,381,920 and leaves 7 left over. A wild integer, folded down into one of eight real slots. That fold is how any key, however large its hash, still names a bucket that exists.

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 only N slots. And the moment you hold more than N keys, two of them must share a bucket by the pigeonhole principle. Long before you even reach that point, birthday-style coincidences already make near-collisions common. So a hash map is really two ideas welded together, and the first is a function that scatters keys evenly across the whole table. The second is a plan for when the scatter lands two keys on the same slot.

Let's make that "birthday-style" claim a real number instead of a hand-wave. Take the smallest live table, 8 buckets, and drop keys into it one at a time. The first key is free, the second dodges it with probability 7/8, the third with 6/8, the fourth with 5/8. Multiply those surviving fractions together: 8/8 × 7/8 × 6/8 × 5/8 = 1680/4096, which is about 0.41. So the chance that four keys land with no collision at all is only 41%. That means a collision is already more likely than not — about 59% — with the table barely half full. That is exactly why the probe path in the next section is not some rare edge case. It is the normal weather of a hash map, and the whole design exists to make it cheap.

There are two classic plans. The first is chaining: each bucket holds a little linked list, and colliding keys hang off the same bucket. The second is open addressing: keep everything in the one flat array, and if your bucket is taken, probe for another. You try a different slot by a fixed rule until you find a free one. CPython's dict uses open addressing. 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 flies). The figure below shows the simplest probe: walk to the next slot. But the real story is deeper. Real CPython uses a perturbed sequence so collisions don't clump.

Here's the subtlety that makes open addressing actually work. When two keys collide and the second one probes forward, a later lookup has to tell them apart. So landing on a bucket is never proof by itself. The map compares the key you asked for against the key stored in that slot. If they don't match, it keeps probing along the exact same path the insert took, until it finds your key or hits an empty slot. This is why each slot caches the hash. Comparing two 8-byte hashes first is cheap, and only when those match does the map do the slower full equality check on the keys. A jump, a hash compare, and maybe a key compare — that's the real anatomy of one lookup.

Let's trace one real lookup so the anatomy stops being abstract. Say "Levels" already lives in bucket 7, and you now insert "Faded", which happens to hash to bucket 7 as well. That slot is taken, so "Faded" probes forward one step to (7 + 1) % 8, which is bucket 0, and settles there. Later you ask the map for "Faded". It jumps to the home bucket 7 and compares the cached hash — that matches, but the full key stored there reads "Levels", so it is not your key. So the map keeps probing, steps to bucket 0, matches the hash again, and this time the key check agrees and hands back your value. Two slots touched, two cheap hash compares, one full key compare. That is a collision costing three extra instructions, not a search.

Build the intuition by driving it. In the widget, pick a key and watch it compute hash % 8 and light its home bucket. Then 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. An empty table sits at 0, and a half-full one at 0.5. As it climbs toward 1.0 the free slots vanish and the probe chains lengthen, so the beautiful O(1) rots into an O(n) scan. The map never lets it get that close. CPython resizes the moment the table would cross two-thirds full. It doubles the bucket array, then rehashes every existing key into the bigger table. It has to, because each key's home bucket is computed as hash % N, and N is exactly the number that just changed.

Let's make that two-thirds concrete with the smallest table. A fresh dict has 8 buckets. Drop in 5 keys and the load factor is 5/8, which is 0.625 — under the line, so nothing happens. Add a sixth key and you'd sit at 6/8, which is 0.75. That crosses two-thirds, so before the sixth key even settles, CPython doubles the array to 16 buckets and rehashes everything. Now those 6 keys live in 16 slots, a load factor of 0.375, and there's room to breathe again. That's the rhythm of the whole structure: fill toward two-thirds, double, fall back to about a third, and repeat.

You can actually watch this happen with sys.getsizeof, which reports how many bytes a live object occupies. So I inserted integers one at a time and printed the size only at the moments it 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, and the table doubles every single time it crosses the line. An empty dict is a bare 64-byte header with no bucket array at all. The first key conjures an 8-slot table that jumps the size to 224 bytes. From there each resize copies every key into a fresh, larger, mostly-empty array, so that copy is O(n). But it happens rarely and the table doubles each time, so the cost amortizes to O(1) per insert. It is the same amortized bookkeeping as the list's overallocation back in Volume 3, where you pay a big bill occasionally to keep every other insert instant.

Here's why that "amortizes to O(1)" is a theorem, not a hope. When you grow to n entries, the biggest copy moved about n keys. The one before it moved about n/2, the one before that n/4, and so on downward. Add that whole chain up: n + n/2 + n/4 + n/8 + … never climbs past 2n. So building an n-entry dict from empty costs at most about 2n copy operations in total, spread across n separate inserts. Divide it back out and that is roughly two copies per insert on average, a constant that does not grow with n. The doubling is what makes the geometric sum collapse to 2n. If the table instead grew by a fixed 8 slots each time, that sum would balloon to O(n) per insert and the whole guarantee would die.

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 price is space. Look back at the layout for a moment. A big fraction of the buckets are deliberately empty, which is just the load factor at work. And each occupied bucket doesn't only hold a value — it holds the hash, plus a reference to the key, plus a reference to the value. A list, by contrast, stores one 8-byte reference per element and nothing else. So the dict stores far more per entry and keeps spare empty slots on top. Here's the same data laid out 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, or 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, about ~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.

Where does that ~37 bytes a slot actually go? Three of the fields are the ones we already named: the cached hash, the reference to the key, and the reference to the value. On a 64-bit build each is 8 bytes, so that is 24 bytes of real payload for every live entry. The remaining ~13 bytes are the tax you pay for speed. Part is a separate sparse index that maps a hash to an entry, and part is the empty headroom the load factor deliberately keeps free. So even a full-looking dict is quietly carrying its own emptiness on the books. That is the space-for-speed trade read straight off in bytes: 24 that hold your data, ~13 that hold the single jump open.

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:

A concrete pair makes the rule stick. Say you're mapping grid positions to whatever sits on them. A coordinate written as a tuple, (3, 7), is a perfectly good key. A tuple of two ints is frozen, so its hash never moves. Write that same coordinate as a list, [3, 7], and Python raises TypeError: unhashable type: 'list' the instant you try to use it as a key. Same two numbers, same meaning to you. The difference is that the list could grow a third element later and change its hash, and the map can't allow a key whose address might drift.

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

Why the hard ban? Picture exactly what a mutable key would do, and suppose the map let you use a mutable object whose hash tracked its own contents. You store value under it and it lands in bucket 4, and a moment later you reach in and mutate that key. Now it hashes to bucket 7 instead. So when you ask the map for that key again, the lookup walks straight to bucket 7, finds nothing waiting there, and simply reports the key as missing. Meanwhile 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.)

So what do you do when the thing you want to key by really is a list? You freeze a copy of it. Turn the list [3, 7] into the tuple (3, 7), or turn a set into a frozenset, and use that frozen version as the key. You're making a promise the map can rely on: this key's contents are fixed, so its bucket is fixed. That's the whole contract in a single line. A key may be anything at all, as long as it swears never to change while the map is holding it.

There is a deeper rule hiding underneath "immutable", and it is worth naming out loud: two keys the map treats as equal must produce the same hash. Think for a second about why that has to hold. The map finds a key by hashing it to a bucket. So if two equal keys hashed to different buckets, storing under one and looking up with the other would miss. The map would swear that a key it is actually holding isn't there. This is the __hash__ and __eq__ contract, and Python's built-in immutable types honor it for free. But when you write your own class and override __eq__ to compare by contents, you must override __hash__ to match. Otherwise you quietly break the invariant every dict silently relies on. Equal keys, equal hashes — that is the whole promise, and a frozen key is just the easiest way to keep it.

$ 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 completely unrelated numbers back. But hash(42) came back as 42 every single time. String hashes are salted per process, which is PYTHONHASHSEED quietly at work. Integer hashes are not, because integers aren't the flooding target. So within one run the same key always lands in the same bucket, but a different run can send it somewhere else entirely. That is also why you should never persist a Python hash to disk and expect it to match on the 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." Once you see it, you see it constantly. Every dict you write, obviously. But also plenty you don't write yourself. Database indexes use it: a hash index turns a WHERE-clause value straight into a row location, with no table scan. Redis and memcached are whole databases that are essentially one giant hash map living in RAM, serving billions of lookups a second. Deduplication drops everything into a set, and collisions reveal the duplicates. A compiler's symbol table maps every variable name to its type and address as it parses your code. And memoization/caching leans on it too: @lru_cache is a dict keyed by your function's arguments.

INPUTfrom collections import Counter, defaultdict

words = ["apple", "avocado", "beet", "cherry", "cabbage", "apple", "beet", "apple"]

# 1. THE MANUAL GROUPING - three lines of bookkeeping you write every time
by_letter = {}
for w in words:
    first = w[0]
    if first not in by_letter:        # the "does the bucket exist yet?" dance
        by_letter[first] = []
    by_letter[first].append(w)
print("manual     :", by_letter)

# 2. setdefault - the same thing, one line, ONE lookup
sd = {}
for w in words:
    sd.setdefault(w[0], []).append(w)
print("setdefault :", sd)

# 3. defaultdict - the bucket is conjured by the factory, no test at all
dd = defaultdict(list)
for w in words:
    dd[w[0]].append(w)
print("defaultdict:", dict(dd))
print("all three equal:", by_letter == sd == dict(dd))

# 4. .get - a read that cannot raise
print("get('a'):", by_letter.get("a", []), "| get('z', []):", by_letter.get("z", []))

# 5. Counter - tallying, already written for you
c = Counter(words)
print("Counter     :", c)
print("most_common(2):", c.most_common(2), "| c['kiwi'] ->", c["kiwi"])

OUTPUTmanual     : {'a': ['apple', 'avocado', 'apple', 'apple'], 'b': ['beet', 'beet'], 'c': ['cherry', 'cabbage']}
setdefault : {'a': ['apple', 'avocado', 'apple', 'apple'], 'b': ['beet', 'beet'], 'c': ['cherry', 'cabbage']}
defaultdict: {'a': ['apple', 'avocado', 'apple', 'apple'], 'b': ['beet', 'beet'], 'c': ['cherry', 'cabbage']}
all three equal: True
get('a'): ['apple', 'avocado', 'apple', 'apple'] | get('z', []): []
Counter     : Counter({'apple': 3, 'beet': 2, 'avocado': 1, 'cherry': 1, 'cabbage': 1})
most_common(2): [('apple', 3), ('beet', 2)] | c['kiwi'] -> 0

A set is the same machinery with the values thrown away. It's 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.

from collections import Counter
import timeit

def first_unique(s):
    """The first character that appears exactly once - or None."""
    counts = Counter(s)          # PASS 1: one walk, every tally landed by hash
    for ch in s:                 # PASS 2: walk the ORIGINAL, in order
        if counts[ch] == 1:      # each test is one jump, not a re-scan
            return ch
    return None

def brute(s):
    """The O(n^2) version, kept only to check the fast one."""
    for i, ch in enumerate(s):
        if s.count(ch) == 1:     # .count re-scans the whole string. Every time.
            return ch
    return None

cases = ["swiss", "aabbcc", "", "z", "python", "redivider", "aabbcdc"]
for s in cases:
    a, b = first_unique(s), brute(s)
    print(f"  {s!r:12} -> {a!r:6}  (brute {b!r})  {'ok' if a == b else 'DIFFER'}")

print("Counter('swiss') =", Counter("swiss"))

setup = ("from __main__ import first_unique, brute\n"
         "import random; random.seed(3)\n"
         "s = ''.join(random.choice('abcdefghij') for _ in range(20_000)) + 'Q'")
tc = timeit.timeit("first_unique(s)", setup=setup, number=50) / 50
tb = timeit.timeit("brute(s)", setup=setup, number=3) / 3
print(f"20,001 chars: Counter two-pass {tc*1e3:6.2f} ms   |   brute .count {tb*1e3:7.1f} ms")
print(f"speedup: {tb/tc:.0f}x")

#   'swiss'      -> 'w'     (brute 'w')  ok
#   'aabbcc'     -> None    (brute None)  ok
#   ''           -> None    (brute None)  ok
#   'z'          -> 'z'     (brute 'z')  ok
#   'python'     -> 'p'     (brute 'p')  ok
#   'redivider'  -> 'v'     (brute 'v')  ok
#   'aabbcdc'    -> 'd'     (brute 'd')  ok
# Counter('swiss') = Counter({'s': 3, 'w': 1, 'i': 1})
# 20,001 chars: Counter two-pass   1.44 ms   |   brute .count   446.8 ms
# speedup: 310x
#   (wall-clock wanders a few percent run to run - a repeat gave 435.4 ms
#    and 302x. The few percent is noise; the 300-fold is the law.)

# WHY PASS TWO IS NOT OPTIONAL. Look hard at that Counter line.
# Counter('swiss') prints as {'s': 3, 'w': 1, 'i': 1} - and 's' is first.
# The dict remembers the order keys were FIRST SEEN, and 's' was seen first.
# That is arrival order, not "appears once" order, and the two are different
# questions. Read the answer off the Counter alone and you would still have
# to skip 's', which means you would still be doing pass two - just badly,
# over the wrong sequence. The string knows the order; the tally knows the
# counts; the answer needs both, which is exactly why it takes two walks.
#
# WHAT THE TWO PASSES COST. Pass one hashes each character once and lands a
# tally: n jumps. Pass two hashes each character once more and reads a
# tally: at most n jumps. So 2n hash-and-jumps, which is O(n) - against the
# brute force's n scans of n characters, O(n^2). The measurement above is
# that gap in the flesh: 1.44 ms against 446.8 ms on 20,001 characters,
# about 310x. Ten times the characters would widen it by another ten.
#
# THE SHAPE TO CARRY AWAY. "Tally in one pass, then decide in a second pass
# over the original order" is one of the most reusable moves you own. First
# repeated character, first non-repeated word, the first duplicate in a log,
# the most recent unique visitor - all the same two passes, all resting on
# the fact that a tally lookup is one jump and never a search.

One honest caveat before you reach for a dict on reflex. The single-jump lookup earns its keep when you look things up by key often and the collection is large. For a handful of items, a plain list you scan is just as fast in practice and far lighter in memory — remember the dict cost four to five times the bytes per item. And a dict answers "what's at this key?" brilliantly, but it's the wrong tool for "what's the smallest?" or "give these back to me in order." Reach for the hash map when the question is reach by label. Reach for something else when the question is really about order or ranking.

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? →