TwiddleLab / Code / Data Structures You Can See
Hash Tables: How Dictionaries Find Things
What you will learn
- A hash function turns a key into a number. The number % the table size picks a locker.
- A hash table stores each key in its locker, so finding it is a jump, not a search.
- Two keys in one locker is a collision; the locker keeps a short chain and checks it.
- A good hash spreads keys evenly; a big enough table keeps chains short. That's how a Python dict stays fast.
How the lesson goes
Instagram finds your account among billions in a blink.
It doesn't check them one by one. Try that way first: find Mia.
What if the name itself said which locker?
Run the hash machine on Mia. Then type your own name.
% 8 gives a remainder from 0 to 7, exactly one per locker. The sum depends only on the letters, so the machine gives the same locker every time you ask.
Be the machine. Put each name in its locker.
The letter sums are on the cards. You do the % 8.
Lockers plus a hash: a hash table.
A hash function turns a key into a number. That number % size picks a locker, also called a bucket.
A hash table is the lockers with keys (and their values) inside. Looking up a key means: hash it, jump to the locker, check what's there.
Two keys in one locker is a collision. Here the locker keeps a short chain, like last lesson's arrows. A Python dict is a hash table too; on a collision it tries another free locker instead of making a chain.
Which hash function is best?
Try all three on the same 10 names. Keep the one that spreads them most evenly, then Check.
Length puts every 3-letter name in one locker, and first letter puts Mia, Max and Milo together. The sum changes when any letter changes, so it spreads names more evenly. Real hash functions mix the bits even harder.
How many lockers do 12 names need?
Slide the number of lockers. Find the fewest where no chain is longer than 2, then Check.
With few lockers, many names must share. Each extra locker gives the sums more room. Python's dict quietly makes its table bigger once it gets about two thirds full, so chains stay short.
Find Zoe: hash table against a plain list.
Step through the lookup. The list search runs when you're done.
A chatbot turns every word into a token number.
It looks words up in a table like this, millions of times a second. Which locker holds "cat"? Tap it, then Check.
cat: 3 + 1 + 20 = 24, and 24 = 3 x 8 + 0. Real language models use a dictionary from token text to token number; it's a hash table under the hood.
Locker sprint.
Five names, one of them yours. Tap each locker as fast as you can.
Previous lesson: Linked Lists: Chains of Arrows · Next lesson: Sets: Is It In There? · Part of the course: Data Structures You Can See
Lessons are interactive and need JavaScript. Turn it on to play them.
