Chapter 5 — Hash Tables: The Magic and the Fine Print

“Hash tables are the most important data structure ever invented… they let you trade space for time, and time is usually what you’re short of.” — attributed to the systems-programming folklore around Donald Knuth’s The Art of Computer Programming, Vol. 3

“To him the gatekeeper opens. The sheep hear his voice, and he calls his own sheep by name and leads them out.” — John 10:3

Why This Matters

Four weeks ago you started counting the cost. Arrays gave you O(1) indexing and a cache that rewards order. Linked lists gave you O(1) splicing and a cache that punishes pointer-chasing. Stacks and queues gave you disciplined interfaces over both. Every one of those structures had an honest, visible cost, and you learned to read it.

This week you meet the structure that looks like it broke the rules.

A hash table promises you something that should be impossible: find any item, by an arbitrary key, in constant time — not O(n), not O(log n), but O(1), the same whether you store ten items or ten million. You already use it. Every time you write a Python dict or a set, you are using a hash table. students["Maya"] returns Maya’s record in roughly the same time it takes to return anybody’s, no matter how many students there are. That feels like magic.

It is not magic. It is a trade — the same speed-versus-memory trade that has run under every chapter of this book — made so cleverly that the cost almost hides. The architect’s job this week is to find the cost, because a tool whose price you can’t see is a tool you will eventually misuse. The hash table’s average O(1) is real and wonderful. Its worst case is O(n), its memory overhead is deliberate and significant, and — most sobering — its worst case can be triggered on purpose by an attacker. All three of those facts are in the fine print, and this chapter is going to make you read every line of it.

Here is the move under the hood, in one sentence: a hash table turns your key into an array index by running it through a hash function, and then it does an O(1) array access. That’s it. The whole structure stands on the array you built in Chapter 2 — contiguous memory, O(1) random access — plus one function that converts “Maya” into “go look in slot 7.” The genius is in that function and in what you do when two different keys want the same slot. Which they will. Always.

The Christian question for the week is the shepherd’s: what does it mean to be called by name? “He calls his own sheep by name and leads them out.” A hash table is, at its heart, a machine for calling things by name — for taking a name and going directly to the one thing it refers to, without searching the whole flock. That the structure can fail to keep names distinct (two keys, one slot) and must be designed to recover gracefully — that, too, has something to say. We’ll come back to it.

5.1 — The dict You Already Use, From the Outside

Start with what you know. In Python, a dict maps keys to values, and a set is a dict with the values thrown away (it stores only keys). You have used both since your first Python rep:

attendance = {"Maya": "present", "Marcus": "absent"}
attendance["Maya"]            # -> "present"     (lookup by key)
attendance["Jonah"] = "late"  # insert / update
"Marcus" in attendance        # -> True          (membership test)
del attendance["Marcus"]      # remove

seen = set()
seen.add("Maya")
"Maya" in seen                # -> True

Every operation on that list — get, put, in, del — is average O(1). Compare that to the alternatives you’ve built. To answer "Maya" in some_list on an unsorted Python list, you scan: O(n). On a sorted array with binary search, O(log n) — but you paid to keep it sorted. The dict answers the same question in constant time, independent of size. That is the whole reason the dict is the most-reached-for non-trivial structure in Python (and Java’s HashMap, and C++‘s unordered_map, and JavaScript’s Object and Map). When you need “find this thing by its name, fast,” this is the tool.

The cost table you’ve been building gets a powerful new row this week:

Read that last block carefully, because it is where the fine print begins. The hash table dominates the first four rows. It loses the last two. A hash table has no idea what “the smallest key” is, can’t give you the keys in order without sorting them, and can’t answer “all keys between 10 and 20” without checking every key. The structure that buys you O(1) by name throws away all order to do it. That trade is the whole reason next week’s chapter on trees exists. Hold the thought.

Coach’s Note — The word “average” in “average O(1)” is doing enormous work, and most people skip right over it. It is not the same as “always,” and it is not the same as the amortized O(1) you learned for append in Chapter 2. Amortized is a guarantee about a sequence. Average here is a probabilistic claim that depends on your keys spreading out nicely — a claim an adversary can break (§5.8). By the end of this chapter you will never again say “O(1)” about a hash table without a small voice adding “…on average, assuming a good hash and no adversary.” Say the whole sentence. That’s the architect talking.

5.2 — Hashing: Turning a Key Into a Bucket Index

The array gives you O(1) access by integer index. buffer[7] is one multiply-and-add (Chapter 2). But your keys aren’t integers — they’re strings like "Maya", or tuples, or whatever. So the central trick of the hash table is a function that converts an arbitrary key into an integer you can use as an index:

bucket_index = hash(key) % number_of_buckets

Two steps. First, hash(key) produces some integer from the key — could be huge, could be negative. Second, % number_of_buckets squashes that integer into the valid range 0 to number_of_buckets - 1, so it’s a legal array index. That index names a bucket — a slot in the underlying array. To store a key, you compute its bucket and put it there. To find it again, you compute the same bucket and look there. No scanning. Direct access. Called by name.

Python hands you the hash function directly. Try it:

hash("Maya")        # some big integer, e.g. -4839204... (varies per run — §5.8)
hash(42)            # 42  (small ints hash to themselves in CPython)
hash(3.14)          # an integer derived from the float
hash((1, 2))        # tuples are hashable (immutable)
hash([1, 2])        # TypeError: unhashable type: 'list'  (mutable!)

That last error is a rule you must internalize: only immutable things can be hash keys. If you could hash a list and then mutate it, its hash would change, and the table would look for it in a different bucket than the one it’s stored in — it would become unfindable. So Python forbids hashing mutable built-ins. (This is exactly why dict keys can be strings, numbers, and tuples, but not lists or other dicts.)

What makes a hash function good? Three properties, and you must be able to recite them:

A great hash function also has a fourth, subtler virtue: avalanche — flipping one bit of the input flips about half the bits of the output. That’s what makes “Maya” and “Maxa” land in totally different buckets instead of adjacent ones, which keeps the distribution uniform even for keys that look almost identical.

# A bad hash for strings (DON'T ship this): sum of character codes.
def bad_hash(s):
    return sum(ord(c) for c in s)

bad_hash("abc")    # 97+98+99 = 294
bad_hash("cba")    # 99+98+97 = 294  <-- COLLISION. "abc" and "cba" clump.
bad_hash("bca")    # 294 again.       Every anagram collides.

bad_hash is deterministic and fast, but it fails uniformity spectacularly: every anagram lands in the same bucket. Real string hashes (like the one inside Python’s hash) mix in position, so order matters and anagrams scatter. Don’t write your own hash for production — but understanding why bad_hash is bad is exactly the understanding the project’s Hard tier will make you exploit.

Coach’s Note — Notice that bad_hash violates only one of the three properties and it’s already useless. Deterministic? Yes. Fast? Yes. But not uniform, and uniformity is the property that protects the O(1). A hash function is a contract, and uniformity is the clause everyone forgets to read until their lookups mysteriously crawl. When you debug a “why is my dict slow” problem in your career — and you will — the answer is almost always “the keys aren’t spreading.”

5.3 — Collisions Are Inevitable (The Pigeonhole Principle)

Here is a fact you cannot engineer your way around. You have a finite number of buckets — say 8. You can store an unlimited number of distinct keys. The moment you have 9 keys and 8 buckets, at least two keys share a bucket. This is the pigeonhole principle: nine pigeons, eight holes, some hole holds two pigeons. No hash function, however brilliant, escapes it. Collisions are not a bug to be eliminated. They are a mathematical certainty to be managed.

And it’s worse than “more keys than buckets.” Even when you have fewer keys than buckets, collisions show up shockingly early, because hashing scatters keys randomly and random scatter clumps. This is the birthday paradox in disguise: in a room of just 23 people, there’s a better-than-even chance two share a birthday, even though there are 365 days. Same math here — with far fewer keys than buckets, two keys probably already collide. You will see this in the project; with 8 keys in 4 buckets, our demo shows chains forming immediately.

So the real engineering question is not “how do I avoid collisions” — you can’t — but “what do I do when two keys want the same bucket?” There are two classic answers, and you will build both. They are the two halves of this chapter.

# Demonstrate the pigeonhole principle directly: 9 keys, 8 buckets, guaranteed collision.
keys = ["a", "b", "c", "d", "e", "f", "g", "h", "i"]   # 9 keys
buckets = [[] for _ in range(8)]                         # 8 buckets
for k in keys:
    buckets[hash(k) % 8].append(k)
# At least one bucket now has 2+ keys. Always. By the pigeonhole principle.
print([len(b) for b in buckets])   # e.g. [1, 2, 1, 1, 0, 2, 1, 1] — some bucket has 2

5.4 — Resolution Strategy 1: Separate Chaining

The first answer is the most intuitive: if multiple keys land in one bucket, let the bucket hold all of them — in a list. Each bucket is not a single slot but a small list (a “chain”) of (key, value) pairs. To look up a key, you find its bucket, then scan that one short list for your key. To insert, you append to the chain (after checking the key isn’t already there). To delete, you remove it from the chain.

class ChainingHashMap:
    def __init__(self, initial_buckets=8, max_load_factor=0.75):
        self._buckets = [[] for _ in range(initial_buckets)]  # array of bucket-lists
        self._size = 0
        self._max_load_factor = max_load_factor

    def _index_for(self, key):
        return hash(key) % len(self._buckets)   # the key -> bucket step

    def put(self, key, value):
        bucket = self._buckets[self._index_for(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                 # key already here -> overwrite
                bucket[i] = (key, value)
                return
        bucket.append((key, value))      # new key -> add to the chain
        self._size += 1
        if self._size / len(self._buckets) > self._max_load_factor:
            self._resize(len(self._buckets) * 2)

    def get(self, key, default=None):
        for k, v in self._buckets[self._index_for(key)]:   # scan ONE bucket
            if k == key:
                return v
        return default

Stop and see why this is fast on average. The lookup does one O(1) bucket access, then scans one chain. If the hash is uniform and you have n keys in m buckets, the average chain length is n/m — a number you control. Keep n/m near 1 (a handful of keys per bucket) and every scan is over a list of length ~1: effectively O(1). The full cost of get is O(1 + n/m) — the 1 for the bucket access, the n/m for the chain scan.

But now see the worst case honestly. If every key hashes to the same bucket — because your hash is terrible, or because an attacker chose the keys (§5.8) — then one bucket holds all n keys and the others are empty. The chain is length n. A lookup scans the whole thing. O(n). Your “hash table” has degenerated into a single linked list with extra steps. The structure is only as good as the distribution its hash produces.

This is the implementation the Normal tier of Project 5 asks you to build. The complete, runnable version is in code/chaining_hashmap.py; run it and watch the collision and resize demos print real numbers.

Coach’s Note — Separate chaining is the strategy taught first because it’s the easiest to reason about and the hardest to get wrong. Deletion is trivial (remove from a list). The load factor can technically exceed 1 (chains just get longer; nothing breaks). Java’s HashMap uses chaining (and, since Java 8, upgrades a too-long chain into a balanced tree to cap the worst case at O(log n) — a clever defense you’ll appreciate after Chapter 6). It’s a great default. The other strategy, next, trades that simplicity for better cache behavior.

5.5 — Resolution Strategy 2: Open Addressing (Linear Probing)

The second answer is sneakier and, on modern hardware, often faster. Open addressing keeps every key directly in the bucket array — one key per slot, no chains, no extra lists. So what happens on a collision, when the slot you want is already taken? You probe: you walk forward to the next slot, and the next, until you find an empty one (to insert) or your key (to find). The simplest probe sequence is linear probing — just step forward one slot at a time, wrapping around the end of the array.

def _slot_for(self, key):
    n = len(self._keys)
    start = hash(key) % n
    for step in range(n):
        i = (start + step) % n     # step forward, wrap around
        if self._keys[i] is EMPTY:
            return i               # found an empty slot (key not present)
        if self._keys[i] == key:
            return i               # found the key
    # ...table full; must have resized before now

To get, you start at hash(key) % n and probe forward until you hit your key (success) or an empty slot (the key isn’t here — because if it were, the probe that inserted it would have stopped before this empty slot). That last bit of reasoning is the whole correctness argument for open addressing, and it has a vicious consequence: deletion is hard.

If you delete a key by just blanking its slot to EMPTY, you might break the probe chain for some other key that was inserted after it and “jumped over” this slot. A later get for that other key would hit the new EMPTY slot, conclude “not here,” and stop early — even though the key is still in the table farther down. The fix is the tombstone: a deleted slot is marked DELETED, not EMPTY. Probes walk past tombstones (the chain stays intact) but inserts may reuse them. It’s a real subtlety, and it’s exactly the kind of fine print open addressing forces on you that chaining doesn’t.

That cache row is why open addressing is often faster in practice despite the tombstone hassle: probing forward through the array is sequential memory access, the cache-friendly pattern from Chapter 2 — the hardware prefetches the next slots you’re about to probe. Chaining chases pointers to scattered heap nodes, the cache-hostile pattern. The asymptotics are the same; the constant factor favors open addressing. This is the Chapter 2 cache lesson showing up exactly where you were promised it would.

But open addressing has a failure mode chaining doesn’t: primary clustering. When slots fill up, occupied slots tend to form long contiguous runs, and any key that hashes into a run has to probe all the way to the end of it. Clusters grow and merge, and probe lengths explode as the table fills. The math is unforgiving: average probes per lookup is roughly ½(1 + 1/(1 − α)) where α is the load factor. At α = 0.5 that’s about 1.5 probes; at α = 0.9 it’s about 5.5; at α = 0.99 it’s about 50. That is why open-addressing tables resize aggressively and keep their load factor low — typically 0.5 to 0.66, far lower than chaining tolerates.

The runnable version is in code/probing_hashmap.py. Its probe_cost_demo measures exactly this curve. When I run it, average probes per lookup climb like this:

Measurement tracks theory. That is the cost of letting the table fill up, made visible. The Medium tier of Project 5 asks you to add this open-addressing implementation behind the same interface as your chaining map and measure both under rising load.

Coach’s Note — “Same interface, two implementations, measured against each other” is the exact pattern from Chapter 4’s stacks and queues, and it is the architect’s pattern. The interface (put/get/remove) is the promise. Chaining and probing are two ways to keep it, with different costs. When you can swap implementations behind a stable interface and measure which one your workload prefers, you are doing the job. The structure is a decision, and a decision is only real when you’ve felt both options.

5.6 — Load Factor and Resizing: The Self-Defending Table

Both strategies share one knob, and it is the most important number in the structure: the load factor.

load_factor = number_of_keys / number_of_buckets

It measures how full the table is. At load factor 0.5, the table is half full and collisions are rare. At 0.9, it’s nearly full and collisions (and chains, and probe runs) are everywhere. A hash table stays fast only while its load factor stays low — that’s the whole game. So the table watches its own load factor and grows itself before it gets crowded, exactly the way the dynamic array in Chapter 2 grew itself before it overflowed. When the load factor crosses a threshold (commonly 0.75 for chaining, 0.5 for open addressing), the table:

1. Allocates a new bucket array, usually twice as big.
2. Re-hashes every existing key into the new array, because the bucket index is hash(key) % number_of_buckets, and the bucket count just changed — so every key’s bucket changes. This step is called rehashing.
3. Throws away the old array.

def _resize(self, new_bucket_count):
    old_buckets = self._buckets
    self._buckets = [[] for _ in range(new_bucket_count)]
    for bucket in old_buckets:
        for key, value in bucket:
            # MUST recompute the index — it depends on the new bucket count.
            self._buckets[hash(key) % new_bucket_count].append((key, value))

That resize is O(n) — you touch every key. So why isn’t the table slow? The same amortized argument as Chapter 2’s dynamic array: doubling means resizes happen rarely (at sizes 8, 16, 32, …), and the total rehashing work across n inserts sums to O(n), spread over n inserts — amortized O(1) per insert. You bank the cost of the rare expensive rehash across all the cheap inserts around it. You already proved this exact sum for the dynamic array; the hash table reuses the proof.

Run code/chaining_hashmap.py and watch the resize demo: as keys go in, the load factor climbs toward 0.75, then the table doubles and the load factor drops back near 0.4, over and over. The table is defending its own O(1) by spending memory on empty buckets the moment it gets crowded.

Coach’s Note — Why grow before it’s full, not when it’s actually full? Because “fast” for a hash table means “uncrowded,” and a half-empty table is uncrowded by design. The empty buckets are not waste — they are the price of speed, paid in memory. This is the speed-versus-memory trade of the whole book, sitting right in the resize threshold. Lower the threshold (resize sooner) and you spend more memory for fewer collisions; raise it and you save memory but invite slowdowns. The threshold is the trade, exposed as a single tunable number. An architect sees that number and knows exactly what dial they’re turning.

5.7 — The Honest Cost: Average O(1), Worst Case O(n), and the Space Bill

Now we write down the fine print in full. No marketing, just the costs.

Time. With a good hash and a controlled load factor:

The average column is why the structure is famous. The worst column is the fine print. The gap between O(1) and O(n) is not a rounding error — at a million keys it is the difference between instant and a million steps. Whether you live in the average column or the worst column depends entirely on whether your keys spread out, which depends on your hash and, crucially, on whether anyone is choosing your keys adversarially (§5.8).

Space. A hash table is a deliberately under-filled array, and that is its space cost. To keep the load factor at, say, 0.66, you keep roughly one-third of your buckets empty at all times — pure overhead, memory holding nothing, bought to keep collisions rare. On top of that, chaining pays for list objects and the per-pair pointers in every chain; open addressing pays for the empty slots and any tombstones. Compare this to an array, which can run 100% full with zero per-element overhead. The hash table trades memory for speed — it spends empty space to buy constant-time lookup. That sentence is the structure in nine words. If memory is your binding constraint and you don’t need by-key lookup, the hash table is the wrong tool because of this space bill.

This is the speed-versus-memory tradeoff in its purest Phase 1 form. The array was tight in memory and O(n) to search by value. The hash table is O(1) to search by key and loose in memory. You don’t get both. You choose, based on which resource the problem makes scarce. Project 5’s measurement memo is where you’ll put numbers on this trade with your own hands.

import sys
d = {}
for i in range(1000):
    d[i] = i
# The dict holds 1000 ints but its internal table has MORE than 1000 slots —
# the spare capacity that keeps the load factor low. That spare capacity is
# the memory you spent to buy O(1). sys.getsizeof(d) reflects the table, not
# the keys/values it points at (recall the boxing lesson from Chapter 2).
print(sys.getsizeof(d))   # noticeably larger than 1000 * 8 bytes

5.8 — Under the Hood: CPython’s dict and Hash Flooding

You’ve built the model. Now look at the real thing you use every day, accurately but at altitude.

CPython’s dict uses open addressing, not chaining — every key lives in one contiguous table, and collisions are resolved by probing (a cleverer probe sequence than plain linear probing, designed to scatter and avoid clustering). It keeps the load factor at 2/3; cross that and it grows. So far, exactly the structure you just studied.

But since Python 3.7, the dict has one more famous property: it remembers insertion order. Iterate a dict and you get keys back in the order you inserted them. (This was an implementation detail in 3.6 and became a language guarantee in 3.7.) That ordering is not something a plain hash table gives you — hashing scatters keys, remember. CPython gets it with the “compact dict” design: the hash table itself stores only small indices into a separate, dense, append-only array of (hash, key, value) entries kept in insertion order. The sparse, under-filled part (the part that costs memory) holds tiny indices instead of full entries, which actually saves memory over the old design, and the dense entries array preserves order for free. It’s a genuinely elegant piece of engineering: faster iteration, less memory, ordered keys — and it’s why your dicts iterate predictably. (A set, by contrast, makes no ordering promise — don’t rely on set iteration order.)

That ordering guarantee does not change the cost table. Lookup is still average O(1) / worst O(n); you still can’t do a range query or get the sorted order (insertion order ≠ sorted order) without paying O(n log n). The compact dict is a better hash table, not a different kind of structure.

Now the dangerous part. Recall §5.4’s worst case: if every key collides, the table degenerates to O(n) per operation. For a long time, hash functions were predictable — hash("attack") returned the same value on every machine, every run. That meant an attacker who knew your hash function could precompute thousands of keys that all collide into one bucket and send them to your server as, say, HTTP form fields or JSON object keys. The server dutifully stores them in a dict, every insert collides, the dict goes O(n²) to build, one CPU core pins at 100%, and the server stops answering legitimate requests. That attack is called hash flooding (or algorithmic-complexity DoS), and it was a real, exploited vulnerability across many languages and web frameworks in 2011 (CVE-2011-3414 and siblings). A single small malicious request could take down a server. The worst case isn’t theoretical; it’s a weapon.

The defense, adopted across languages, is hash randomization: mix a random per-process seed into the hash function at startup, so the hashes (and therefore the buckets) are unpredictable from one run to the next. An attacker can no longer precompute colliding keys, because they don’t know the seed. CPython enables this by default for str and bytes keys. You can see it:

python3 -c "print(hash('attack'))"
python3 -c "print(hash('attack'))"
# The two numbers DIFFER — the per-process random seed changed.
# (Set PYTHONHASHSEED=0 to disable randomization and watch them match — don't
#  do that on a server facing untrusted input.)

Run code/flooding_demo.py to see the worst case happen. It builds a table with a deliberately terrible hash (every key to bucket 0) and times the same workload against a good hash. The good hash scales linearly; the bad hash’s time roughly quadruples each time you double n — the O(n²) signature of building a table where every operation is O(n). That’s the attack, in your terminal.

Coach’s Note — This is your first taste of a theme that dominates Phase 2: untrusted input changes the cost analysis. When you control the keys, “average O(1)” is a fair description. When an adversary controls the keys, the worst case is the expected case, because the adversary will deliberately steer you into it. The architect who builds a public server thinks about the worst case the way the architect who builds a private tool thinks about the average case. We are flagging it now, in Phase 1, so that when you stand up a real server in Week 9 and accept JSON from strangers, the words “hash flooding” are already in your vocabulary and “randomized hash” is already your default. The cost of a structure is not a fixed fact — it depends on who gets to choose its inputs.

5.9 — When a Hash Table Is the Right Tool (and When It Isn’t)

The architect chooses. Here is the decision, sharp.

Reach for a hash table (dict / set) when:

• You need fast lookup by an arbitrary key. “Give me the record for user "maya42".” This is the home turf. O(1) average, nothing beats it.
• You need fast membership tests on large data. “Have I seen this value before?” A set answers in O(1); a list takes O(n). This single swap turns many accidental O(n²) loops into O(n).
• You need deduplication. set(my_list) removes duplicates in O(n). Counting occurrences? dict or collections.Counter. Grouping by a key? dict of lists. These are the daily idioms hash tables exist for.
• You don’t care about order (or insertion order is enough — CPython gives you that for free on dict).

Reach for something else when:

• You need keys in sorted order, or min/max/predecessor/successor. A hash table scatters keys by design; getting them sorted costs O(n log n) every time. The right tool is a balanced search tree (Chapter 6, next week), which keeps keys ordered and gives O(log n) lookup and O(log n) min/max/range.
• You need range queries — “all keys between 10 and 20,” “everything alphabetically from ‘M’ to ‘P’.” A hash table has to check every key (O(n)); it has no notion of “nearby.” A tree walks exactly the matching range in O(log n + k). This is the reason databases offer tree-based (B-tree) indexes alongside hash indexes — a forward link to the persistence chapters in Phase 2.
• Memory is the binding constraint and you don’t need by-key lookup. The hash table’s empty-bucket overhead (§5.7) is dead weight you can’t afford. A tight array or a sorted array may be the answer.
• You’re accepting keys from untrusted input and can’t guarantee a randomized hash. Then the worst case is the threat model (§5.8); design accordingly.

Notice the shape of the decision: hash table for membership and by-key lookup with no ordering; tree for anything that needs order. That single sentence is the bridge into Chapter 6. The hash table answers “is this here, and what’s its value?” The tree answers “what’s around this, and in what order?” Different questions, different tools, both built on the same arrays you started with in Chapter 2.

5.10 — Common Bugs

The bugs that bite when you use hash tables — and the ones that bite when you build one.

Bug: Using a mutable object as a key, then mutating it. The key’s hash changes and it becomes unfindable. Example: Using a list as a dict key (Python forbids this with TypeError) — or, more insidiously, a custom object whose __hash__ depends on a field you later change. After the mutation, d[obj] raises KeyError even though obj is “in” the dict. Fix: Hash keys must be immutable, or at least their hashable fields must never change while they’re in the table. Use tuples, strings, numbers, or frozen/immutable objects as keys.

Bug: Forgetting to recompute the index during resize — rehashing into the old bucket count. Example: In _resize, writing self._buckets[hash(key) % old_count] instead of % new_count. Keys land in wrong buckets; later lookups (which use the new count) miss them. Fix: The bucket index always depends on the current bucket count. After resize, every index must be recomputed against the new size. This is why rehashing is unavoidable and why resize is O(n).

Bug: Deleting from an open-addressing table by blanking the slot to EMPTY instead of marking it DELETED. Example: Insert A, B, C that all probe through slot 5. Delete B by setting slot 5 to EMPTY. Now a lookup for C hits the EMPTY slot, stops early, and reports C missing — though C is still in the table. Fix: Use a tombstone (a distinct DELETED marker). Probes walk past tombstones; inserts may reuse them. Chaining doesn’t have this problem (just remove from the list) — it’s the price of open addressing.

Bug: Treating n in some_list as cheap inside a loop, building an accidental O(n²) program. Example: for x in items: if x in seen_list: ... where seen_list is a Python list — each in is O(n), so the loop is O(n²). Fix: Make seen_list a set. Membership goes O(n)→O(1) and the loop goes O(n²)→O(n). This is the single most common real-world use of a hash table and the most common missed optimization.

Bug: Relying on set iteration order, or assuming dict iteration gives sorted order. Example: for k in my_set: and expecting a stable order — sets make no order guarantee. Or expecting for k in my_dict: to yield sorted keys — it yields insertion order, not sorted. Fix: If you need sorted order, sorted(my_dict) (O(n log n)) or use a tree (Chapter 6). If you need stable insertion order, that’s dict (3.7+), not set.

Bug: Assuming hash-table lookup is always O(1) and being surprised by a latency spike or a slow server under load. Example: A profile shows dict operations dominating; the cause is either a bad/clustering hash (rare) or adversarial colliding keys from untrusted input (§5.8). Fix: It’s average O(1), not worst-case O(1). For untrusted keys, ensure hash randomization is on. For custom-object keys, make sure your __hash__ actually spreads. Measure the distribution (bucket_lengths() in your impl) when in doubt.

5.11 — Reps

Open the exercises for the full set. This week’s reps build the muscles the project needs: computing bucket indices by hand, forcing collisions on purpose, feeling the load-factor/resize dance, and watching the worst case appear. AI stays OFF — Phase 1. You cannot reason about an attack on a structure you have never built and broken yourself.

A preview:

• Rep 1 — Compute hash(key) % m by hand for several keys and predict the buckets; confirm in the REPL.
• Rep 4 — Build the chaining put/get and write a test that forces two keys into one bucket.
• Rep 7 — Instrument resize: print buckets and load factor as you insert, find every doubling point.
• Rep 10 — Make the worst case appear: hash every key into bucket 0, then time the quadratic blowup as n doubles.

Do every one. The reps are the conditioning; the project is the game.

5.12 — This Week’s Project

You’re ready for Project 5 — Build a Hash Map, in Project 5.

Normal tier: implement a separate-chaining HashMap from the starter — put, get, remove, __len__, a hash-to-bucket function, and automatic resize when the load factor crosses a threshold — with tests that include a real collision (two keys you know share a bucket). Medium tier: add a linear-probing implementation behind the same interface, then measure both under rising load factor and show where each degrades. Hard tier: construct an adversarial set of keys that all collide under your hash, demonstrate the O(n) worst case in measurements, then fix the hash and watch the worst case vanish — and write up why this exact attack (hash flooding) is a server-security concern, a forward link to Phase 2.

Like every Phase 1 project, it ends in a measurement memo. The code is half the grade; the honest accounting of cost — average vs worst, time vs space, and what an adversary changes — is the other half.

5.13 — Coach’s Final Word for Week 5

This week you looked under the most useful structure you own. You learned that the dict’s magic is a hash function turning a name into an array index, standing on the O(1) array you built in Week 2. You learned that collisions are not a bug but a certainty — the pigeonhole principle guarantees them — and that the whole art is in resolving them, by chaining or by probing. You learned that the table defends its own speed by watching its load factor and resizing before it crowds, paying for O(1) in empty memory. And you learned the fine print the brochures skip: average O(1) is a probabilistic claim that an adversary can break, turning your fast table into an O(n) crawl on purpose.

You did not memorize “dict is O(1).” You earned the whole sentence: average O(1), worst case O(n), amortized on insert, paid for in space, and only safe against adversaries with a randomized hash. That sentence is the architect talking.

If the average-versus-worst gap feels abstract: that’s the gap to close. Run the flooding demo, watch the time quadruple, and the worst case stops being a footnote and becomes something you can feel. Close it.

The shepherd calls his sheep by name and leads them out — he goes directly to the one he means, not searching the whole flock. That is the hash table’s gift and its picture: to be called by name is to be found at once, distinctly, not lost in the crowd. And when two names would collide in one place, a well-built table does not lose either one — it keeps both, distinct, recoverable. There is something right about a structure whose deepest design problem is how never to lose a name.

See you on Monday.

Up next: Read the exercises and complete every rep. Then open Project 5 and build your hash map. After that, Chapter 6 — trees, where hierarchy is the shape and order is the thing the hash table threw away to go fast.

Previously: Chapter 4 — stacks, queues, and deques: disciplined interfaces over arrays and lists.