The trick: compute where, don't search
Every structure so far searches for an item. A hash table refuses to search at all. It runs the key through a hash function that computes an array index directly, then stores the value there. Look-up repeats the computation and jumps straight to the slot — O(1) on average, independent of how much data there is.
This is how dictionaries, maps, sets and caches work in every language. When you write students["roll42"], a hash function is turning "roll42" into an array position behind the scenes.
What makes a good hash function
A hash function must be deterministic — the same key always gives the same index — and it should spread keys uniformly across the array so they do not pile up. Typically it turns the key into a large number and takes it modulo the array size.
It does not need to be reversible or secret (that is cryptographic hashing, a different job). Here the only goals are speed and an even spread.
Collisions, and how to handle them
Two different keys will sometimes hash to the same slot — a collision. They are unavoidable (more possible keys than slots), so every hash table needs a plan for them. Two standard ones:
Chaining — each slot holds a small linked list; colliding keys just join the list at that slot. Open addressing — on a collision, probe to the next free slot (linear probing) and store there.
O(1) is an average, not a promise
With few collisions, look-up is O(1). But if a bad hash function sends many keys to one slot, that slot's list grows and look-up degrades toward O(n). The average is excellent; the worst case is why the hash function and load factor matter.
Load factor and resizing
The load factor is items ÷ slots. As it climbs, collisions climb with it and performance sags. So hash tables resize: when the load factor passes a threshold (often around 0.7), the table allocates a bigger array and rehashes every key into it. That occasional rehash is what keeps the everyday operation at O(1).
A worked example
A hash table has 10 slots and hashes a key by (sum of letter positions) mod 10. Insert keys hashing to 3, 7 and 3 using chaining. What happens?
- First key → slot 3. Second key → slot 7. Both sit alone.Distinct slots, no collision yet.
- Third key also hashes to 3 — a collision with the first.Two different keys mapped to the same index.
- With chaining, slot 3 becomes a short list holding both keys; look-up walks that tiny list.Chaining stores colliding keys together and searches only within the slot.
Slot 3 holds a two-item list, slot 7 holds one. Look-up stays fast because each list is tiny — until the load factor rises and the table resizes.