Crafting Interpreters · Week 11
Crafting Interpreters 20: Hash Tables: reading guide
Read the chapterVerified by tests
A hash table from scratch with open addressing and linear probing, FNV-1a hashing, tombstones for deletion, growth by load factor, and string interning so string equality becomes pointer equality.
Time About 7 hours this week
Why it matters
Hash tables are the most used data structure in practice. Building one yourself demystifies every dictionary and map you use, and Knuth 6.4 later analyzes exactly this design.
How to approach it
Implement, then write a small stress test that inserts and deletes many keys and checks lookups. Re-read the tombstone section twice; it is the subtle part.
Challenges
3 challenges at the end of the chapter.
Challenge 1 (support non-string keys) and challenge 2 (tune and compare hash table designs) are great; challenge 3 (benchmarking) pairs well with 2.
Traps
- Not treating tombstones correctly on insert versus lookup.
- Infinite loop when the table has no empty slots (load factor too high).
- Counting tombstones in the load factor or not, inconsistently.
Verified by the book's chap20_hash tests when you push your repo.