Hash table
A hash function turns a key into a bucket number, here the remainder after dividing by 7. Storing a key and finding it again both start by jumping straight to its bucket, so a lookup only searches the few keys that share it.
14229314401327
Store 8 keys, then look up 13. Press play or step forward to start.
1function buildAndFind(keys, target) {2 const buckets = Array.from({ length: 7 }, () => []);3 for (const key of keys) buckets[key % 7].push(key);4 const bucket = buckets[target % 7];5 for (const key of bucket) {6 if (key === target) return true;7 }8 return false;9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | keys spread evenly: about one key per bucket |
| average | 1 | a good hash and enough buckets |
| worst | n | every key lands in the same bucket |
| space | n | one entry per key, plus the buckets |
Where it breaks
- Collisions. Two keys with the same remainder share a bucket, and a lookup has to walk that bucket's list. Pick All collide: every key is 1 more than a multiple of 7, so finding 50 checks all 8 keys, as slow as a linear search.
- Too few buckets. With more keys than buckets, collisions are guaranteed. Real hash tables grow, usually doubling the bucket count, when they get about three quarters full, so buckets stay short.
- No order. Buckets follow the hash, not the value. To list keys in order or find the smallest, a hash table does not help: use a sorted array or a search tree.