Finding something without searching
You have a million usernames and need to know if ada is one of them. Checking them one by one could take a million steps. A sorted list and binary search gets that down to about twenty.
A hash table does it in about one step, no matter how many there are. It is the structure behind Python's dict, JavaScript's Map and objects, Java's HashMap, and most caches and database indexes.
The trick: let the key itself tell you where it is stored.
Keep a row of numbered buckets
A plain array. Bucket 0, bucket 1, bucket 2, and so on.
Turn the key into a number
A hash function takes the key and produces a number. The same key always gives the same number.
Use that number to pick a bucket
Divide by the number of buckets and take the remainder.
Store it there, and look for it there
To find the key later, do the same sum and go to the same bucket. No other bucket is touched.
Watch it fill up
The hash below is simple enough to check by hand: add up the letters (a = 1, b = 2, c = 3, ...) and take the remainder after dividing by 8.
Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.
- Keys stored
- 0
- Longest bucket
- 0
- Extra checks
- 0
Example
Where does cat go?
c = 3, a = 1, t = 20. That adds up to 24. 24 divided by 8 leaves a remainder of 0. So cat lives in bucket 0, and anyone looking for cat will do the same sum and look in bucket 0.
Two keys, one bucket
In the animation, dog and owl both landed in bucket 2. That is a collision. Collisions are unavoidable: there are far more possible keys than buckets. A hash table needs a plan for them, and there are two common ones.
Chaining
Each bucket holds a small list. Colliding keys go into the same list, and a lookup walks that list. This is what the first animation does.
Linear probing
Each bucket holds one key. If the bucket is taken, try the next one, then the next, until a free one turns up. A lookup walks the same way until it finds the key or hits an empty bucket.
Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.
- Keys stored
- 0
- Longest bucket
- 0
- Extra checks
- 0
Probing keeps everything in one flat array, which computers read very quickly. Watch what happens near the end, though. Keys that could not get their own bucket fill up the neighbours, which pushes later keys further still. A run of full buckets forms and every new key that lands in it makes it longer. hen wanted bucket 3 and ended up in bucket 7.
Is it always one step?
"Hash tables are O(1)" is true on average, with a good hash function. Here is the same table with keys chosen to defeat our simple hash. They are anagrams: the same letters in a different order, so the letter sum is identical.
Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.
- Keys stored
- 0
- Longest bucket
- 0
- Extra checks
- 0
Every key is in bucket 2. Finding one means walking the whole list, exactly like the slow search we were trying to avoid. In the worst case a hash table is just a list.
Real hash functions mix the bits thoroughly so that similar keys land far apart, and many languages add a random secret so that attackers cannot craft colliding keys on purpose.
Try the combinations
Start. Eight empty buckets, numbered 0 to 7. The hash: add up the letters (a = 1, b = 2, ...) and take the remainder after dividing by 8.
- Keys stored
- 0
- Longest bucket
- 0
- Extra checks
- 0
What it is good and bad at
Good at
- Insert, find and delete in about one step on average
- Works with any key that can be hashed: text, numbers, tuples
Where it bites
- No order: you cannot ask for the smallest key or the next key after this one
- Slow in the worst case, when many keys collide
- Uses extra memory, because it must stay partly empty to stay fast
Key takeaways
- A hash table turns the key into a bucket number, so it goes straight to the right place.
- Two keys in one bucket is a collision. Chaining keeps a list per bucket. Probing uses the next free bucket.
- Probing is fast in memory but forms runs of full buckets as the table fills.
- Tables resize when they get too full, to keep lookups short.
- O(1) is the average case. With bad luck or a bad hash, one bucket holds everything.