Chapter 4 of 10All chapters
Chapter 4 of 10
Hash maps and sets
The structure to reach for first.
How they work
A hash function turns a key into a slot number, so lookups skip searching entirely. Average cost is constant; the worst case degrades when many keys collide.
- Keys must be hashable, which usually means immutable.
- There is no order, so never rely on how a map iterates.
Sets
A set is a map without values, and it turns quadratic duplicate-finding into a single pass. Reaching for one is the most common real speedup in ordinary code.