TAOCP 6.4 Hashing (part 2): reading guide

Part 2 covers open addressing (linear probing, double hashing), deletion with open addressing, the detailed analysis of probe counts as tables fill up, and comparisons between methods.

Time About 9 hours this week

Why it matters

Open addressing with linear probing is what many modern high-performance hash tables use. Knuth's linear probing analysis is historically the start of the field of algorithm analysis.

Before you start

6.4 Hashing (part 1)

How to approach it

Compare this with your clox hash table from chapter 20: tombstones, load factor, linear probing. Measure probe counts at load factors 0.5, 0.75 and 0.9 and compare to Knuth's formulas.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

Deleting by just clearing a slot breaks later searches. Tombstones or Knuth's deletion algorithm fix this.
Letting the load factor get close to 1 with linear probing.