TAOCP 6.4 Hashing (part 1): reading guide

Part 1 covers the first half of the section: choosing hash functions (division and multiplicative methods, including the golden-ratio multiplier) and collision resolution by separate chaining, with analysis.

Time About 8 hours this week

Why it matters

Hash tables are the most used data structure in practice. Knowing why a bad hash function wrecks performance will save you in production.

Before you start

6.1 to 6.3
1.2.4 Number theory

How to approach it

Implement multiplicative hashing and test it against keys with patterns (all multiples of 64, sequential IDs). Implement a chained hash table and measure chain lengths against the theoretical averages.

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

Using a power-of-two table size with a weak hash: only low bits get used.