Project 5 — Build a Hash Map

“Fear not, for I have redeemed you; I have called you by name, you are mine.” — Isaiah 43:1

Chapter: 5 — Hash Tables: The Magic and the Fine Print Due: End of Week 5 Submit: A link to your code — a public GitHub repo URL — containing your source, tests, and README.txt. See Appendix A for the local Python + git toolchain and the repo workflow. Allowed tools: Python 3, the standard library (time, sys, random, tracemalloc), a non-AI editor, the textbook. AI: Phase 1 (wk 1–8): AI is OFF. No assistants of any kind. You cannot reason about the cost of a structure — or the attack on a structure — that you have never built yourself. Phase 2 (wk 9–16) turns agentic AI on with a required agent-log.txt; this is not that.

The Setup

A growing church runs a check-in system for its weekday children’s ministry. Every child has a unique tag ID, and at peak drop-off the volunteers need to answer one question, instantly, hundreds of times in a few minutes: given this tag, who is this child and which room are they in? The current code does a linear scan of a list of every enrolled child — fine at fifty kids, painfully slow now that enrollment crossed a thousand, and the line at the door is backing up.

You’ve diagnosed it: this is a by-name lookup problem, and a linear scan is the wrong tool. The right tool is a hash map — O(1) average lookup by tag, no matter how many children are enrolled. The ministry director, once bitten by a “fast” system that mysteriously crawled during the Christmas rush, has one demand: show me, in numbers, that it stays fast — and tell me honestly when it wouldn’t.

So you won’t just hand them a dict. You’ll build the structure yourself, prove its costs with measurements, and — at the Hard tier — show exactly how a hash map can be made slow on purpose, so the ministry understands the one scenario where it could fail and why the standard defense protects them. The shepherd calls each sheep by name; your job is to build the machine that does it, and to be honest about its fine print.

The scale is intentionally small. The discipline of building, measuring, and reading the fine print is identical at any size.

Learning Targets

By completing this project, you will demonstrate that you can:

• Implement a hash map with separate chaining: buckets, a hash-to-index step, put/get/remove, and load-factor-triggered resize with rehashing.
• Write tests that include a real collision (two keys you know share a bucket) and prove correctness under it.
• Implement a second strategy — open addressing with linear probing — behind the same interface, including correct tombstone deletion.
• Measure both implementations under rising load factor and report where each degrades.
• Construct an adversarial key set that triggers the O(n) worst case, demonstrate it in timings, and fix it.
• Write a measurement memo that names the speed-versus-memory trade and the security implication of the worst case (hash flooding).

Normal Tier

Goal: Build a working separate-chaining HashMap from the provided starter, with tests that include a forced collision and a verified resize.

Start from code/hashmap_starter.py. Do not wrap a Python dict — the whole point is to build the thing a dict is. You may use a Python list as your raw bucket array and as the chains.

Required features

1. Hash-to-bucket step. _index_for(key) returns hash(key) % number_of_buckets. (Handle the fact that hash() can be negative — % by a positive count already does.)
2. put(key, value) — overwrite if the key is present (no duplicate), else add to the chain and increment size.
3. get(key, default=None) — scan the key’s bucket; return the value or the default.
4. remove(key) — remove the pair; raise KeyError(key) if absent.
5. __len__ and __contains__.
6. Load factor + automatic resize. When size / buckets exceeds a threshold (default 0.75), double the bucket count and rehash every key into the new array. Track a resizes counter.
7. A test file (test_hashmap.py) with at least 8 tests, including:
   • put/get round-trip for several keys;
   • overwrite (same key twice) does not grow len;
   • remove of a present key and of an absent key (KeyError);
   • a forced collision: two keys you know land in the same bucket (assert _index_for(a) == _index_for(b)), both stored, both retrievable, and removing one leaves the other intact;
   • a resize test: insert enough keys to cross the threshold and assert resizes >= 1 and that every key is still retrievable after the resize.

Example output

$ python3 hashmap_demo.py
put 1000 children, load factor stayed at 0.62, resizes: 7
get tag "T0042": ("Maya L.", "Room 3")    [O(1) average]
get tag "T9999": not enrolled
longest chain: 4   (good spread — no key is far from O(1))

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. Open addressing behind the same interface

Add a second implementation, ProbingHashMap, with the exact same public interface (put/get/remove/__len__/__contains__) using open addressing with linear probing. It must:

• store keys directly in the slot array (no chains);
• probe forward (wrapping) on collision;
• delete correctly with tombstones (a removed-then-re-added key must still be findable);
• keep its load factor low (default threshold 0.5) and resize by doubling.

Your existing test file must pass against both implementations with no changes — write the tests against the shared interface, then run them against each class. (This is the Chapter 4 “one test suite, multiple backings” pattern.)

M2. Measure both under rising load factor

Write benchmark.py that, for each implementation, builds a non-resizing table and measures average lookup cost (probes for probing; chain length scanned for chaining) at load factors 0.25, 0.5, 0.75, 0.9. Produce a table:

                load=0.25  load=0.50  load=0.75  load=0.90
chaining  avg scan  1.12       1.25       1.38       1.45
probing   avg probe 1.21       1.47       2.27       4.93

Then time real get workloads for both and report wall-clock. Note which strategy wins at low load (probing — cache locality) and where probing’s clustering makes it degrade faster near full. One paragraph relating your numbers to §5.5.

Hard Tier (+up to 25% additional extra credit)

H1. Trigger the worst case, then kill it

Construct a deliberately adversarial set of keys that all collide under your map’s hash function, and demonstrate the O(n) worst case in measurements:

1. Make your map’s hash function swappable (a constructor argument), as in code/flooding_demo.py.
2. Build a colliding key set (e.g., all keys whose hash(key) % m is the same — easiest with a deliberately bad hash that returns a constant, or by exploiting a weak hash you can predict).
3. Time put+get workloads at n = 1000, 2000, 4000 with the bad hash. Show the time roughly quadrupling as n doubles (the O(n²) signature) and the longest chain equal to n.
4. Replace the bad hash with a good one and re-run. Show the time merely doubling and the longest chain dropping to a small constant. The worst case vanished.

H2. The security memo (the part an agent cannot write for you)

Write MEMO.docx, the deliverable that is the point of the whole project. It must:

1. Report your measurements from M2 and H1 as tables, with a one-line read of each.
2. Name the speed-versus-memory trade concretely: from your own numbers (use sys.getsizeof and/or tracemalloc), how much memory does keeping the load factor low cost, and what does that memory buy in lookup speed? Show a load factor where the table is faster but wastes more space, and one where it’s tighter but slower.
3. Explain hash flooding in your own words: how an attacker who controls the keys (e.g., HTTP form fields, JSON object keys) can force the worst case on a server, why this is a denial-of-service vector, and how hash randomization (a per-process random seed, on by default in CPython for strings — §5.8) defeats it. Reference the real 2011 hash-DoS incident.
4. Make the architect’s call: for the ministry check-in system specifically — keys are tag IDs you generate, not attacker-supplied — is hash flooding a real threat here? Defend your answer. Then state the one change to the threat model (hint: where do the keys come from?) that would flip your answer — a forward link to the public server you build in Phase 2.

Point 4 is the judgment piece. There is no single right answer; there is a defensible answer, and the defense is the grade.

Submission

Submit one URL — a public GitHub repo. It must contain:

1. hashmap.py — your HashMap (chaining) and, for Medium+, ProbingHashMap.
2. test_hashmap.py — the test suite (passing against both implementations for Medium+).
3. benchmark.py (Medium+) and flooding.py (Hard) — the measurement scripts.
4. MEMO.docx (Hard) — the measurement-and-security memo.
5. README.txt — your reflection:

# Project 5 — Build a Hash Map

**Tier targeted:**  Normal / Medium / Hard
**Features done:**  (list)
**Collision strategy:**  separate chaining (+ open addressing if Medium+)
**Resize policy:**  threshold ___, growth ___x
**Worst case demonstrated:**  yes / no — where (Hard)
**Speed-vs-memory note:**  (one line — what the empty buckets buy you)
**What I learned:**  (one paragraph)
**What I'd change:**  (one sentence)
**AI usage:**  NONE — Phase 1.  Signed: <your name>

6. Reflection comment block at the top of hashmap.py — same fields, condensed.
7. The code left runnable — the grader runs python3 -m pytest (or python3 test_hashmap.py) and your tests pass; running benchmark.py/flooding.py reproduces the tables in your memo.

Hints (Read Before You Begin)

• Build chaining first, completely, with tests, before you touch probing. A working, tested chaining map is the whole Normal tier and the foundation for everything above. Don’t start probing until chaining is green.
• Forcing a collision is easy with integer keys. With m buckets, 0 and m collide (both % m == 0), as do 1 and m+1, etc. Use that for your collision test — no need to fight string-hash randomization.
• The rehash is where resize bugs live. After doubling, recompute every key’s index against the new bucket count. If a post-resize get misses, this is almost certainly your bug (§5.6, and Rep 8).
• Tombstones, not blanks. For probing, deletion must mark a slot DELETED (a distinct sentinel), never EMPTY, or you’ll break the probe chain for other keys. Test: remove a key, re-add it, confirm it’s still findable. See code/probing_hashmap.py.
• Make timings honest. Use time.perf_counter, run a warm-up pass, time enough operations that the numbers are stable, and report the methodology in your memo. A measurement you can’t reproduce is an opinion.
• For the adversarial set, the constant hash is the clearest demo. lambda key: 0 sends every key to one bucket — the unambiguous worst case. A “predict a real weak hash’s collisions” approach is more impressive but harder; either earns H1 if the O(n²) signature shows in your timings.

What Mastery Looks Like (Beyond the Rubric)

A great Project 5 doesn’t just work — it proves things. Its tests don’t merely check that get returns a value; they force a collision and prove both keys survive, they trigger a resize and prove no key is lost in the rehash. The benchmark doesn’t just print numbers; it prints the curve — average lookup cost rising with load factor — and the memo reads that curve back to the reader in one honest sentence.

A great Project 5 treats the worst case as the main event, not a footnote. Anyone can show a hash map is fast; you’ll be one of the few who can make it slow on purpose, watch the O(n²) signature appear in the timings, and then make it fast again by fixing the hash. That demonstration — average O(1) and worst-case O(n), both in the same script, the gap visible in milliseconds — is the difference between someone who uses hash tables and someone who understands them.

And a great memo makes the architect’s call without flinching. It doesn’t say “hash flooding is bad, use a good hash.” It says: for this system, with these keys, here is whether the threat is real, here is my reasoning, and here is the exact change that would flip my answer. That conditional, constraint-driven judgment — “it depends, and here is precisely what it depends on” — is the whole book in one paragraph.

Coach’s Note — Students often build the chaining map in an evening and think they’re done. The chaining map is the easy half. The week’s real lesson — and the project’s real grade — is in the measurements and the memo: feeling the load factor in your timings, watching the worst case appear, and saying out loud what the structure costs and when it fails. Code that runs is table stakes. Code that taught you what it costs is the assignment.

When You’re Done

1. Run your tests. All green, against both implementations if you went Medium+.
2. Run benchmark.py. Confirm the load-factor curve matches the shape in §5.5.
3. Run flooding.py (Hard). Confirm the bad-hash time quadruples as n doubles, then vanishes with the good hash.
4. Read your own MEMO.docx slowly. Could the ministry director — a non-programmer — understand from it why the system stays fast and the one scenario where it wouldn’t? If not, rewrite it for that reader.
5. Submit.
6. Read Chapter 6. Trees next — the structure for everything the hash table threw away to go fast: order, range, min/max, predecessor/successor.

A theological footnote. “I have called you by name, you are mine.” The whole point of a hash table is to take a name and go straight to the one it refers to — never lost in the crowd, never confused with another. And when two names would land in the same place, a well-built table refuses to lose either; it keeps both, distinct, recoverable. There is a quiet rightness in that. The structure whose deepest design problem is how never to lose a name is doing, in silicon, a small echo of the shepherd who counts the ninety-nine and goes after the one. Build it so it loses no one.

See you next week.