Start here: the problem it solves#
TL;DRthe 30-second version
- A hash table is an array plus a hash function. Hash the key to a number, take it modulo the array size, and that is the slot. Store and lookup are one slot read each: O(1) on average.
- Two keys can land in the same slot. That is a collision. With linear probing you walk to the next slot until you find a free one, or the key you want.
- The load factor is entries divided by slots. As it climbs, probes get longer. Past a threshold (Java uses 0.75), the table doubles and every entry is rehashed.
- A resize is O(n), but doubling makes it rare enough that inserts stay O(1) amortized.
If the keys were the integers 0, 1, 2 and so on, there would be no puzzle. Put each value in an array at that index, and a lookup is one array read. But real keys are strings like "alice", or long IDs. You can't use "alice" as an array index.
The obvious fixes are too slow. Keep the pairs in a list and scan for the key: that is O(n), a full walk on every lookup. What we want is the array's one-step lookup, for keys that aren't array indices.
The mechanism: hash to a slot, probe past collisions, grow before it fills#
The first step is to turn the key into an array index ourselves. That is what a hash function does. It takes any key and returns a number, fast, and the same key always gives the same number. A good hash spreads different keys across the whole number range as evenly as if it were random.
The hash is a huge number, far bigger than the array. So take it modulo the array size: bucket = hash(key) % capacity. Store means compute that bucket and write the pair there. Lookup means compute the same bucket and read it.
Collisions are guaranteed, because there are far more possible keys than slots. The simplest fix keeps everything in one flat array. It is called open addressing with linear probing. If a key hashes to bucket 5 and bucket 5 is taken, look at bucket 6. If that is taken, bucket 7, then wrap around to 0. The key goes in the first free slot you reach.
walt also hashes to bucket 5, but eve is already there, so walt probes to bucket 6
Lookup follows the same walk from the home bucket. If it reaches an empty slot, stop: the key is not in the table, because the insert would have filled that slot before moving on.
That rule has a catch in deletion. Delete eve by emptying bucket 5, and a later lookup for walt hashes to 5, finds it empty, and wrongly stops. walt is sitting right there in bucket 6. The fix is a tombstone: mark the slot as deleted, not empty. Lookups probe past it. Inserts can reuse it.
Now the last pressure. As you add keys the table fills, and every collision pushes a key further from its home. The measure of fullness is the load factor: entries divided by slots.
So pick a threshold and grow when an insert would cross it. Java's HashMap grows at 0.75; Python's dict grows at two-thirds full. Growing means allocating an array of double the size and reinserting every entry. You can't just copy the slots across, because each key's bucket is hash % capacity, and capacity just changed. Every entry gets rehashed into a new bucket.
the same keys, recomputed as hash % 16
Complexity: why it is O(1), and what the load factor costs#
Store, lookup, and delete are O(1) on average and O(n) in the worst case. The gap between average and worst is set almost entirely by the load factor, written α.
Knuth's analysis of linear probing gives the expected probes per lookup at each load factor.
| Load factor α | Avg probes (found) | Avg probes (not found) |
|---|---|---|
| 0.50 | ~1.5 | ~2.5 |
| 0.75 | ~2.5 | ~8.5 |
| 0.90 | ~5.5 | ~50.5 |
| 0.95 | ~10.5 | ~200.5 |
This table is why resizing exists. Below three-quarters full, every operation is a handful of probes.
The resize looks like it should break the O(1) claim, since rehashing every entry is O(n). Doubling saves it. Between one resize and the next you insert as many keys as the table already held, so the one-time O(n) is spread across that many cheap inserts. That is amortized analysis, the same argument that makes a growable array's append O(1). Grow by a fixed amount instead and you would resize far too often.
PredictYou insert 1,000,000 keys into a hash table that starts with 16 slots and doubles whenever it gets full. Roughly how many total entry-copies do all the resizes cost?
Hint: How many times does the table double to reach a million? What does each resize copy: the whole table, or just what it held at that moment?
About 2,000,000 copies, only twice the final size. The table doubles about 16 times to go from 16 slots to over a million (2^20 ≈ 1,048,576). Each resize copies only the entries present at that moment: 16, then 32, then 64, and so on. That series sums to just under 2,000,000, because a doubling series always sums to about twice its last term.
If this comes up in an interview#
Is a hash table lookup really O(1)? I've heard it can be O(n).
Both are true. It is O(1) on average with a good hash and a bounded load factor. It degrades to O(n) when every key collides into one chain, from a bad hash, adversarial input, or a table left too full. Java 8 softens the worst case to O(log n) by turning a bucket's chain into a red-black tree once it passes 8 entries.
Why can't I just empty a slot when I delete a key?
Because a later key may have been placed by probing past that slot. A lookup for it would hit the now-empty slot, conclude the key is absent, and stop early. So open addressing leaves a tombstone: a marker that lookups probe past and inserts may reuse.
Why does the whole table have to be rehashed on a resize?
Because a key's bucket is hash % capacity, and the resize changes the capacity. A key in bucket 5 of an 8-slot table belongs in hash % 16 of the 16-slot table, which is usually a different bucket. Every entry has to be re-placed against the new size.
When would you not use a hash table?
When you need ordered operations: a range of keys, the smallest key, or sorted iteration. A hash table scrambles key order. A B-tree or skip list keeps keys sorted at O(log n) per operation.
Trade-offs, and the other ways to handle collisions
Reach for a hash table whenever you need a value by its exact key and don't care about order: caches, dictionaries, symbol tables, de-duplication, counting, and joining two datasets on a key. It is the wrong choice the moment order or ranges enter.
| Hash table | Balanced BST | Skip list | Sorted array | |
|---|---|---|---|---|
| Lookup by key | O(1) average | O(log n) | O(log n) expected | O(log n) |
| Insert / delete | O(1) average | O(log n) | O(log n) expected | O(n) (shift) |
| Ordered ops (range, min, next) | No | Yes | Yes | Yes |
| Worst case | O(n) | O(log n) | O(n) (rare) | O(log n) read |
| Memory locality | Good (open addressing) | Poor (scattered nodes) | Poor (scattered towers) | Excellent (packed) |
| Best home | Unordered key lookup | Ordered, strict bound | Ordered + concurrent | Static, read-mostly |
Inside the hash table family, the big split is how collisions are handled. This page built open addressing. The alternatives:
- Separate chaining: each bucket holds a small linked list, and colliding keys go into it. It tolerates high load factors and needs no tombstones, but each collision is a pointer chase to scattered memory. Java's HashMap uses it, with a default capacity of 16.
- Cuckoo hashing: two hash functions and two possible buckets per key, so a lookup checks just two slots and is O(1) in the worst case. Inserts can cascade as keys kick each other out.
- Swiss tables: open addressing with a one-byte fingerprint per slot, scanned a group at a time with SIMD instructions. Google's Abseil, Rust's hashbrown, and Go 1.24's map use it. Datadog reported the Go switch cut their map memory by hundreds of gigabytes.
Failure modes and gotchas
- A weak hash. If keys cluster into a few buckets, operations slow even at a low load factor. A related trap: capacity is almost always a power of two so that hash % capacity becomes a fast bitwise AND, but that mask only looks at the hash's low bits. Java's HashMap XOR-folds the high bits down first.
- Primary clustering. Linear probing builds long runs of occupied slots, because each collision extends a run and makes the next collision more likely. Quadratic probing, double hashing, and Robin Hood hashing exist to avoid this.
- Tombstone buildup. Under heavy deletes the table fills with tombstones that lookups still probe past, so it slows even when the live count is low. Count tombstones as occupancy and rehash into a clean array once they pass a threshold.
- The resize pause. Doubling is amortized O(1), but the one insert that triggers it pays the full O(n). Redis avoids the stall by rehashing incrementally: it keeps the old and new tables side by side and migrates a few buckets per operation.
- Hash flooding (HashDoS). An attacker who knows your hash function can craft thousands of keys that collide into one bucket, turning every lookup into an O(n) scan. The defense is a randomized, keyed hash such as SipHash, now the default in Python and Rust.
- Mutating a key after inserting it. The key was placed by its hash at insert time. Change it and the lookup computes a different bucket and never finds it. Hash keys should be immutable: strings, numbers, frozen tuples.
References & further reading
- Wikipedia — Linear probing — Knuth's probe-count analysis, primary clustering, and tombstone deletion
- OpenJDK — HashMap.java source — real defaults: capacity 16, load factor 0.75, TREEIFY_THRESHOLD 8, high-bit spreading
- CPython — dictobject.c source — the dict: open addressing, power-of-two size from 8, resize at two-thirds full
- Datadog — How Go 1.24's Swiss Tables saved us hundreds of gigabytes — Go's move from chaining to Swiss Tables, with real memory numbers