Hash Tables

Hash Tables: Finding Maya's Coat Without a Ticket: Hash Tables, Why Is Everyone on Hook 3? Hash Functions, Collisions: Two Coats, One Hook.

Updated

  1. 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.
  2. 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.
  3. 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.