Don't memorize the hash table — watch it drop keys into buckets. A hash function turns each key into an array index, so lookups jump straight to the right slot in O(1). Then two keys land in the same bucket — a collision — and you see exactly why they chain, and why a full table slows down.
Turns a key into a bucket index — the same key always maps to the same slot.
BUCKET
One slot of the backing array. Ideally it holds just one entry.
COLLISION
Two keys hash to the same bucket. Unavoidable — so it must be handled.
LOAD FACTOR
Entries ÷ buckets. Too high and chains grow, so the table resizes.
hash-table.sim — insert 8 keys into 7 buckets
Ready
Seven empty buckets, eight keys to insert. Press Insert to hash the next key and drop it into its bucket — and watch what happens when two keys want the same slot.
hash(key) = (Σ char codes) mod 7
0
Inserted
0
Collisions
0.00
Load factor
Why lookups are instant
A plain array is fast if you know the index and slow if you have to search for a value. A hash table gives you the best of both: it computes the index from the key. Store “Guido”, and the hash function turns it into bucket 0; ask for “Guido” later, hash it again, get 0, and jump straight there. No scanning — that's the O(1).
01
Hash the key
Run the key through a hash function to get a number, then take it mod the bucket count to land inside the array.
02
Drop it in the bucket
Store the entry at that index. Insert, search and delete all start by hashing to the bucket — so all three are average O(1).
03
Handle collisions
When two keys share a bucket, keep a small list there (separate chaining). Lookups check that short list — still tiny, as long as the hash spreads keys evenly.
04
Resize before it's full
As the load factor climbs, chains lengthen. Past a threshold (~0.75) the table allocates a bigger array and rehashes everything, restoring short chains and O(1).
Search / Insert / Delete
O(1) avg
Worst case (all collide)
O(n)
Space
O(n)
Resize threshold
~0.75
The catch: a hash table has no order. Iterating it gives keys in bucket order, not sorted order — if you need sorted keys or range queries, reach for a balanced tree instead. And O(1) is an average: a bad hash function or an adversarial set of keys can pile everything into one bucket and drop you to O(n).
SOLVE IT YOURSELF
Solve it: first unique character
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement first_unique(s): return the index of the first character in the string that appears exactly once, or -1 if there is none. Count characters with a hash map, then scan once more — O(n), two passes.
HINTS — 4 IDEAS
A hash map of char → count tells you, in O(1), how many times any character appears.
First pass: walk the string and tally every character into the map.
Second pass: walk again and return the index of the first character whose count is 1.
If no character has a count of 1, return -1.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · Why is a hash-table lookup O(1) on average?
Hashing the key gives the index straight away — you jump to the bucket instead of scanning, which is the whole point.
2 · What is a collision?
Because there are more possible keys than buckets, different keys sometimes map to the same slot — resolved by chaining or probing.
3 · What happens as the load factor gets too high?
More entries per bucket means longer chains and slower lookups, so the table grows its array and rehashes to bring the load factor back down.
Questions
Where are hash tables actually used?
Everywhere: Python dict/set, JavaScript Map/objects, Java HashMap, database indexes, caches, de-duplication, counting frequencies, and the two-sum interview classic. Any time you need “does this exist?” or “what's the value for this key?” fast, it's a hash table.
Chaining vs open addressing?
Chaining stores a list per bucket — simple and degrades gracefully. Open addressing keeps everything in the array and probes for the next free slot on a collision — more cache-friendly but needs careful deletion and a lower load factor. Both are widely used.
What makes a good hash function?
It spreads keys uniformly across buckets, is fast to compute, and is deterministic (same key → same bucket). Poor hashes that clump keys into a few buckets turn your O(1) table into an O(n) list.
You just built instant lookup.
Hash to a bucket, chain on collisions, resize before it fills. The structure behind every dictionary you've ever used.