Hash Tables
A coat check that hands you a numbered ticket: how a hash table turns a key into a place to look, what happens when two coats land on one hook, and why it grows.
Updated
Hash Tables
- Finding Maya's Coat Without a Ticket: Hash Tables (Apprentice): Find a coat by its owner's name in one step, at a coat check with 3,000 coats and no tickets: why a list, an A-to-Z rack and hooks by first letter all fall short, and the structure that fixes them, the hash table.
- Why Is Everyone on Hook 3? Hash Functions (Journeyman): Pick a recipe that turns a name into a hook number without crowding the hooks: three recipes tried on one coat check, the three things a good one has to do, and the multiply-by-31 recipe your language's own hash codes use.
- Collisions: Two Coats, One Hook (Journeyman): Keep every coat when two names land on the same hook: why refusing the coat, taking the next free hook and starting with a huge rack each fall short, and the plan most hash tables use instead: chaining, the load factor and resizing.
Exercise: Build a Coat Check
- Exercise: Build a Coat Check (Journeyman): The paper tickets ran out, and 3,000 coats are coming: build a coat check that hands any coat back in a moment however full it gets, keeps every coat when two names share a hook, and moves to a bigger room before it slows down. The tests check it, collisions and a busy night included.