Chapter 5 — Reps

Conditioning, not grading. Python hash-table reps this week.

Ground rules:

1. Type every line yourself. No copy-paste, especially of the hash math — you need it in your fingers.
2. Run everything. Open a python3 REPL and a scratch file. When a rep says “predict,” write your prediction down before you run it. The gap between your prediction and the truth is the rep.
3. AI stays OFF. Phase 1. You are building the structure you will later trust an agent to use — and you cannot audit an agent’s hash-table choice if you have never built one, broken one, and watched it degrade.
4. Keep your code. Several reps build directly toward Project 5’s HashMap. Save your files; you’ll reuse them.

A note on hash(): CPython randomizes hash() for strings per process (§5.8), so a string’s hash changes between runs. That’s expected and good. For reproducible reps, either work with integer keys (whose hash is stable) or set PYTHONHASHSEED=0 for a single session — but never on a real server.

Reps 1–3: Hashing by Hand

Rep 1 — Key to Bucket

In the REPL, with a table of m = 8 buckets, compute hash(key) % 8 for each of these integer keys (integer hashes are stable, so your numbers will match across runs): 0, 5, 8, 13, 16, 21, 100, 1000.

For each, write down by hand which bucket it lands in before you run it. (For small non-negative ints, hash(n) == n in CPython, so this is just n % 8.) Then confirm:

for k in [0, 5, 8, 13, 16, 21, 100, 1000]:
    print(k, "->", hash(k) % 8)

Which keys collided? You should see at least two share a bucket. Name the colliding pairs and explain why (what do they have in common mod 8?).

Rep 2 — The Pigeonhole, Live

Write a function that takes a list of keys and a bucket count m, and returns the list of bucket lengths:

def bucket_lengths(keys, m):
    buckets = [0] * m
    for k in keys:
        buckets[hash(k) % m] += 1
    return buckets

Call it with 9 integer keys and m = 8. Confirm at least one bucket has 2+ keys — the pigeonhole principle in action. Then call it with m = 4 and the same 9 keys. How much worse is the worst bucket? Write one sentence connecting your observation to §5.3.

Rep 3 — A Bad Hash and Why It’s Bad

Type the bad_hash from §5.2 (sum of character codes) and prove it fails uniformity:

def bad_hash(s):
    return sum(ord(c) for c in s)

Find three different strings that all bad_hash to the same value (hint: anagrams). Then show that Python’s real hash gives them different values. Write one sentence: which of the three good-hash properties (deterministic, uniform, fast) does bad_hash satisfy, and which does it violate?

Reps 4–6: Build Separate Chaining

Rep 4 — Minimal Chaining put/get

From scratch, write a minimal chaining map — no resize yet, fixed at 8 buckets:

class MiniMap:
    def __init__(self, m=8):
        self._buckets = [[] for _ in range(m)]
    def _index_for(self, key):
        return hash(key) % len(self._buckets)
    def put(self, key, value):
        ...   # overwrite if present, else append to the chain
    def get(self, key, default=None):
        ...   # scan the one bucket

Implement put and get. Test: put 5 keys, get them all back. Then put an existing key with a new value and confirm get returns the new value (overwrite, not duplicate).

Rep 5 — Force a Collision and Prove It Still Works

Using your MiniMap (8 buckets), find two integer keys that you know land in the same bucket (from Rep 1 — e.g. 0 and 8, since 0 % 8 == 8 % 8 == 0). Put both. Then:

1. Confirm both are retrievable with the correct values.
2. Inspect self._buckets and confirm both pairs are sitting in the same bucket list.

Write the assertion that proves it:

m = MiniMap(8)
m.put(0, "zero")
m.put(8, "eight")
assert m._index_for(0) == m._index_for(8)   # same bucket — a real collision
assert m.get(0) == "zero" and m.get(8) == "eight"   # both survive

This collision test is exactly what Project 5’s Normal tier requires. Keep it.

Rep 6 — Add remove and __len__

Extend MiniMap with remove(key) (raise KeyError if absent) and __len__. Test:

1. Put 3, len is 3.
2. Remove 1, len is 2, the removed key is gone, the others remain.
3. Remove a key not present → KeyError.
4. Remove one of your colliding keys from Rep 5 and confirm the other colliding key is untouched. (This is where a buggy remove would damage the wrong pair — prove yours doesn’t.)

Reps 7–8: Load Factor and Resize

Rep 7 — Watch the Resize

Add a load-factor check and a _resize(new_m) to your map (double the buckets, rehash everything). Then instrument it: insert 40 keys and, after each insert, print size, bucket count, and load factor. Mark the inserts where the bucket count doubles.

for i in range(40):
    m.put(f"key{i}", i)
    print(f"size={len(m):>2} buckets={m.num_buckets:>3} load={m.load_factor:.2f}")

Confirm the load factor climbs to your threshold, then drops sharply when the table doubles. At what sizes did the doublings happen? (Compare to code/chaining_hashmap.py’s resize demo.)

Rep 8 — The Rehash Bug, On Purpose

In your _resize, deliberately introduce the classic bug: rehash using the old bucket count instead of the new one. Insert enough keys to trigger a resize, then try to get a key inserted before the resize. Watch it fail (return the default / miss).

Then fix it (recompute the index with the new count) and confirm the same get now succeeds. Write one sentence explaining why the bucket index must be recomputed against the new count — connect it to §5.6.

(Breaking it on purpose, then fixing it, is how you make the rule permanent.)

Reps 9–10: Open Addressing and the Worst Case

Rep 9 — Linear Probing by Hand

On paper (or in comments), trace a linear-probing table with 8 slots, all EMPTY. Insert these integer keys in order, computing hash(k) % 8 and probing forward on collision: 5, 13, 21, 6.

• 5 → slot 5 (empty) → goes in slot 5.
• 13 → 13 % 8 = 5 → occupied → probe to slot 6 → empty → slot 6.
• 21 → 21 % 8 = 5 → occupied → 6 occupied → slot 7 → slot 7.
• 6 → 6 % 8 = 6 → occupied → slot 7 occupied → wrap to slot 0 → slot 0.

Draw the final array. Notice how 6, which “should” be at slot 6, got pushed all the way to slot 0 — that’s primary clustering, and it’s why probe lengths grow as the table fills. Then verify your trace against code/probing_hashmap.py.

Rep 10 — Make the Worst Case Appear

Write a deliberately terrible hash (def evil(key): return 0 — every key to bucket 0) and a tiny chaining map that takes a hash function as an argument (model it on code/flooding_demo.py’s TinyMap). Build it with the evil hash, insert n = 1000, 2000, 4000 keys, and time n lookups for each.

1. Record the times. Confirm that doubling n roughly quadruples the time (the O(n²) signature: O(n) per op × n ops).
2. Now do the exact same workload with Python’s real hash. Confirm the time merely doubles (true O(n) total).
3. Print the longest chain in each case.

Write two sentences: what is the worst case of a hash table, and what real-world situation (§5.8) would let an attacker cause it?

Rep 11 — set vs list for Membership

Prove the single most common real-world hash-table win. Build a list of 50,000 integers and a set of the same integers. Time 10,000 membership tests (x in collection) against each:

import time
data = list(range(50_000))
data_set = set(data)
targets = [49_999] * 10_000   # worst case for the list: the last element

Time x in data (list) and x in data_set (set) for the targets. Report both times and the ratio. Then write one sentence: a loop doing if x in some_list for each of n items is O(?); swapping the list for a set makes it O(?).

Done? One Last Thing.

From scratch, no looking — write a function first_duplicate(items) that returns the first value in items that appears more than once (scanning left to right), or None if all are unique. Use a set to do it in O(n) time:

def first_duplicate(items):
    seen = set()
    for x in items:
        if x in seen:        # O(1) average membership
            return x
        seen.add(x)
    return None

Then answer, in writing:

1. What is the time complexity, and why does the set make it O(n) instead of O(n²)?
2. What is the space cost, and how does it embody the speed-versus-memory trade of §5.7?
3. Under what input could this degrade toward the worst case, and what (§5.8) protects you in practice?

If you can write first_duplicate cold and answer all three questions, you have the week. The structure, its average cost, its space bill, and its fine print — all in one ten-line function.

Up next: Project 5 — Project 5: Build a Hash Map.