Foundations · Module 5
Hash tables
Find any key in constant time on average: hash it, pick a slot, handle collisions, resize before it fills.
Hash tables are the reason "look it up" is fast in almost every program you will write: dictionaries, sets, caches, database indexes and symbol tables all start here. This module builds one from the ground up, from turning a key into a number to growing the table before it fills.
- 1What a hash function doesA hash function turns any key into a fixed-size number, quickly and the same way every time. Everything a hash table does starts there.12 min
- 2Turning a key into a slotA hash table keeps its entries in one array. The hash, cut down to the array's size, says which slot a key belongs in.12 min
- 3Collisions: when two keys want the same slotTwo keys can land on the same slot. Linear probing stores the second one in the next free slot, and lookups follow the same path.14 min
- 4Resizing and load factorAs a table fills, collisions pile up. Tables track their load factor and, past a limit, move every entry into an array twice the size.13 min
- 5Hash maps in your languagePython, Java, JavaScript, Go, C++ and Rust all ship a hash map. They differ in how they resolve collisions and what they promise about order, and they share the same traps.14 min