Chapter 18. Hash Tables, Exceptions, and the Search Study

Learning objectives

After this chapter you should be able to:

Do unaided:

Draw a chained hash table for given keys and a given hash function, compute its load factor, and draw what a resize does to its memory.
Write find, insert and rehash for a chained table by hand, and predict when resizes happen and how many entries they move.
Explain why a hash function can be weak on structured keys such as sensor IDs, predict the bucket distribution, and check it with a histogram.
Write throw, try and catch with the standard exception types, trace which destructors run during unwinding, and explain the basic and strong exception-safety guarantees.
Design a timing experiment with warm-up, repetitions, medians, input sizes from 10³ to 10⁶, fixed seeds and a harness the agents cannot change.

May delegate:

The PA6 implementations from your spec (binary search, the hash table, and Chapter 17's BST, stn::SensorIndex, measured under random and sorted insert orders), written by a Writer agent and checked in one of the four configurations of Section 18.4.

Opening case

A composite case, not a real student or course.

Sam has a test network of 300 field stations. Each station carries a temperature, a humidity and a pressure sensor, so the sensor IDs run 1001, 1002, 1003, 2001, 2002, 2003, and so on up to 300003: 900 sensors. The wind gauges are not installed yet. Sam wants the latest reading for any sensor in constant time and asks a Writer agent for stn::ReadingTable, a hash table keyed by sensor ID.

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Team phase.

PredictThe bucket histogram for your hash on your keys, the resizes and moves for 10⁶ inserts, each structure's log-log slope.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 17 · Predict in Chapter 19 →
Writefind, insert_or_assign and rehash by hand, and the PA6 linear scan.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 17 · Write in Chapter 19 →
SpecifyThe PA6 header and tests, find's pointer lifetime, the exception guarantees, the complexity budget; freeze the harness.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 17 · Specify in Chapter 19 →
DelegateThe class experiment: same spec, six calls, four configurations, relaying only.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Team Team phase: several agent sessions work in separate roles (Writer, Reviewer, Tester). You direct them and make the final call.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 17 · Delegate in Chapter 19 →
AuditHidden tests, sanitizers, Valgrind, histogram, three timing runs and slopes against your derivations; every review finding classified with evidence.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 17 · Audit in Chapter 19 →
DefendThe load factor, the input that breaks the hash, what a resize does to memory, what the plot shows.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 17 · Defend in Chapter 19 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

A weak hash function on structured keys

How to catch it Bucket histogram of real keys; a bound on the longest chain; lookup time across sizes

Section 18.3.1 · Timing and log-log plots

Resizing bugs: chains kept at old indexes, references or pointers used across a resize or chain growth

How to catch it Tests across several resize thresholds, finding every key, under ASan

Section 18.3.2 · AddressSanitizer, Tests

Timing claims with no data; a harness edited by the agent; results the optimizer can delete

How to catch it Harness output, not claims; the seven parts of Section 18.1.9; sha256sum before and after

Section 18.3.3 · Build tools

What the chapter covers

18.1 The concept, by hand
- 18.1.1 From searching to computing an address
- 18.1.2 Collisions and chaining
- 18.1.3 Load factor and the cost of a lookup
- 18.1.4 Resizing: what a resize does to memory
- 18.1.5 What makes a hash function good
- 18.1.6 stn::ReadingTable in code
- 18.1.7 Exceptions: throw, try and catch
- 18.1.8 Exception safety: the basic and the strong guarantee
- 18.1.9 Designing a timing experiment
18.2 Predict and check
18.3 What agents get wrong here
- 18.3.1 Weak hash functions on structured keys
- 18.3.2 Resizing bugs
- 18.3.3 Timing claims with no data
18.4 Working with the agent
- 18.4.1 The four configurations
- 18.4.2 Protocol
- 18.4.3 What the experiment can and cannot tell you
18.5 Lab: The PA6 search study
18.6 Defend it

Cost thread

The cost thread ends with a derived bound for each structure set against a measured slope.

Summary

With α = n/m, a chained lookup costs about 1 + α/2 comparisons, but only if the hash spreads your keys as if at random.
On IDs of the form station × 1,000 + k, id % 1000 used 4 of 16 buckets and the identity hash 8; a multiply-and-fold mixer used all 16. Only a histogram or a timing run reveals a weak hash.
Doubling keeps α bounded at linear total cost (1,016 moves for 1,000 inserts from 8 buckets), but a resize holds old and new storage at once and invalidates every pointer into the table, as does a vector chain's own growth.
Unwinding runs every local destructor, so RAII cleans up on the error path. The basic guarantee keeps objects valid; the strong guarantee leaves them unchanged, usually via a copy and a swap that cannot throw.
A defensible timing experiment has a prediction, sizes 10³ to 10⁶, fixed seeds, warm-up, repetitions, medians with spread, a used result, an optimized build and a frozen harness. In the reference run the weak hash was 85 times slower than binary search at 10⁵.
The class experiment compares four agent configurations under one call budget; its results are the class's to collect and defend.

Key terms

bucket: one slot of a hash table's array, holding the entries whose keys hash to it.
hash function: a function that computes a number from a key, used to choose the key's bucket.
collision: two different keys that select the same bucket.
separate chaining: handling collisions by keeping in each bucket a chain of all entries that hash there.
load factor: entries divided by buckets, α = n / m; the average chain length.
rehash: building a larger bucket array and moving every entry to its bucket in the new array.
hash quality (spread): how evenly a hash distributes a given key set over the buckets.
mixing hash: a hash in which every output bit depends on every input bit.
exception: an object thrown to report a failure, carried up the call stack to a matching catch handler.
stack unwinding: leaving each active function after a throw, running the destructors of its local objects.
exception safety: what a function promises about the state it leaves when an exception escapes it.
basic guarantee: after an exception, nothing leaks and every object is valid, though values may have changed.
strong guarantee: after an exception, the state is exactly as it was before the call.
no-throw guarantee: the function never throws, stated with noexcept.
warm-up run: an untimed first pass that pays for cold caches before measurement starts.

Companion code

12 files for this chapter, compiled with the book's flags.

Read the code Download ch18.zip

Connections

Where this chapter and another point to each other most often.

Chapter 14: Resource Ownership: RAII, the Rules of Zero, Three, and Five, and Smart Pointers
The vectors own all the memory, so the rule of zero applies (Chapter 14).
Chapter 16: Templates and the Standard Library
Lookup is any callable taking an ID (Chapter 16).
Chapter 17: Binary Search Trees
No agent is involved. ### 18.1.1 From searching to computing an address A linear scan makes about n/2 comparisons to find a present key; binary search and a balanced BST make about log₂ n, 20 for a million readings (Chapters 10 and 17).
Chapter 19: Directing a Team of Agents
Before treating "no defects found" as good news, check whether the reviewer looked at what matters (Chapter 19). ## 18.5 Lab: The PA6 search study Question. For n from 10³ to 10⁶ records (in this harness, one record per sensor), how does the time to look up a reading by sensor ID grow for a linear scan, binary search on a sorted array, a BST and a hash table, and does each match the bound you derived?

See it on the map

18 Hash Tables, Exceptions, and the Search Study