Start here: the problem it solves#
TL;DRthe 30-second version
- A hash table is an array plus a hash function. To store a key, you hash it to a number, take that number modulo the array size to get a bucket, and put the value there. Lookup does the same arithmetic and reads one slot — that is the O(1).
- Two keys can hash to the same bucket (a collision). With open addressing and linear probing, you just walk to the next slot until you find a free one on insert, or the key you want on lookup.
- The load factor is how full the table is: entries divided by slots. As it climbs, probe chains get longer and lookups slow down. So when it crosses a threshold (Java uses 0.75), the table grows.
- Growing means allocating a bigger array and rehashing every entry into it, because the bucket depends on the array size and the size just changed. A resize is O(n), but because the table doubles, it happens rarely enough that inserts stay O(1) amortized.
You have a few million key→value pairs — usernames to profiles, product IDs to prices — and you need a value back the instant you have its key. How do you find one key among millions without scanning?
If your keys happened to be the integers 0, 1, 2, and so on, there would be no puzzle at all: put each value in an array at that index, and a lookup is a single array read. An array is the fastest lookup structure there is, because reading element i is direct — the machine computes one address and fetches it. The problem is that real keys are not small integers. They are strings like "alice", or long IDs, or arbitrary objects. You cannot use "alice" as an array index.
The naive fixes are all too slow. Keep the pairs in a list and scan for the key: that is O(n), and at a few million keys every lookup walks the whole list. Keep them sorted and binary-search: that is O(log n), better, but every insert now has to shift elements to stay sorted, which is O(n) again. Neither gives you fast lookup and fast insert together.
What we want is the array's one-step lookup, but for keys that are not already array indices. That one wish forces the whole design.
The mechanism: hash to a slot, probe past collisions, grow before it fills#
The forced 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, quickly and deterministically, so the same key always produces the same number. A good hash spreads different keys across the whole number range as evenly as if it were random, so no region of the array gets crowded while another sits empty.
The hash is usually a huge number, far bigger than our array. To turn it into a slot, we take it modulo the array size: bucket = hash(key) % capacity. For a table with 8 slots, every key lands in one of buckets 0 through 7. Storing a pair means computing that bucket and writing the key and value there; looking a key up means computing the same bucket and reading it. Both are a single step, which is exactly the array-speed lookup we wanted.
hash("carol") = 1728614162, and 1728614162 % 8 = 2, so carol lives in bucket 2
Collisions are not a rare accident; they are guaranteed. There are far more possible keys than slots, so by the pigeonhole principle some keys must share a bucket. Worse, collisions show up much sooner than you would guess — the birthday paradox means that even a table that is only part-full will already have keys landing on top of each other. A hash table is defined as much by how it handles collisions as by how it hashes.
The simplest scheme that keeps everything in one flat array is open addressing with linear probing. If a key hashes to bucket 5 and bucket 5 is already taken, you look at bucket 6. If that is taken too, bucket 7, then wrap around to 0, and so on, until you find a free slot. The key gets stored in the first free slot you reach. Its "home" bucket is where it hashed to; where it actually lives may be a little further along, pushed there by the collision.
- PUT: hash the key and take it modulo capacity to get the home bucket.
- If that slot is empty, store the key and value there — done.
- If it holds a different key, step to the next slot (wrapping past the end) and check again. Repeat until you find an empty slot, and store there.
- If along the way you find the same key, it is an update: overwrite the value in place and leave the size unchanged.
Lookup follows the exact same walk. To GET a key, hash it to its home bucket and start checking slots. If a slot holds the key, you found it. If a slot is empty, you can stop: had the key been inserted, the probe on insert would have filled this very slot before moving on, so an empty slot means the key is not in the table. That is why an empty slot ends the search — it is the proof of absence.
walt also hashes to bucket 5, but eve is already there — so walt probes to bucket 6
There is one catch waiting in deletion. If you delete eve by simply emptying bucket 5, then a later lookup for walt hashes to 5, finds it empty, and wrongly concludes walt is absent — even though walt is sitting right there in bucket 6. Emptying the slot broke the probe chain that ran through it. The fix is a tombstone: instead of clearing the slot, mark it as deleted-but-occupied. Lookups probe straight past a tombstone; inserts are allowed to reuse it. The slot is a stepping stone the chain still needs.
Now the last pressure. As you add keys, the table fills, and probe chains get longer — every collision pushes a key further from its home, so more slots must be checked per operation. Push it near full and lookups crawl. The measure of how full the table is is the load factor: the number of entries divided by the number of slots. The whole speed of a hash table hangs on keeping the load factor low.
So we set a threshold — commonly around 0.7 to 0.75 — and when adding an entry would push the load factor past it, we grow. Growing means allocating a larger array, usually double the size, and reinserting every existing entry into it. This last part is the step people forget: you cannot just copy the slots across, because each key's bucket is hash % capacity, and capacity just changed. Every entry has to be rehashed into the bigger table, landing in a new bucket. This is the resize, and it is the signature move of a hash table.
the same keys, recomputed as hash % 16 — most land in brand-new buckets because the capacity changed
Go deeperWhy capacity is usually a power of two, and what a real hash looks like
Taking hash % capacity requires a division, which is relatively slow. When the capacity is a power of two, the modulo becomes a bitwise AND with (capacity − 1), which is far faster — so almost every production hash table keeps its capacity a power of two and doubles on resize. The risk is that AND with a power-of-two mask only looks at the low bits of the hash, so a hash whose low bits are not well mixed causes clustering. Java's HashMap defends against this by XOR-folding the high bits of the hash down into the low bits before masking.
The hash function itself has to be fast and spread keys evenly. A common choice for strings is FNV-1a, which folds the bytes of the key into a 32- or 64-bit number with a multiply and an XOR per byte. The simulator on this page uses FNV-1a so the numbers are real: hash("carol") = 1728614162, and 1728614162 % 8 = 2. Cryptographic hashes like SHA-256 spread even better but are far too slow for this hot path; hash tables use cheap, non-cryptographic hashes and accept the small chance of clustering.
Complexity: why it is O(1), and what the load factor costs#
Store, look up, and delete are all O(1) on average, and O(n) in the worst case. Space is O(n): the array holds n entries plus some empty slack, and the load factor sets how much slack. The average and the worst case are far apart, and the gap is governed almost entirely by the load factor.
For open addressing with linear probing, Knuth's classic analysis gives the expected number of slots a lookup probes as a function of the load factor α. A successful search costs about ½(1 + 1/(1 − α)) probes; an unsuccessful search costs about ½(1 + 1/(1 − α)²). The shape is what matters: the cost is flat and small while α is moderate, then explodes as α approaches 1.
| 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 the whole reason resizing exists. At a load factor of 0.5 a missing key costs about 2.5 slot reads; at 0.9 it costs about 50; at 0.95 it costs about 200. Keeping the table below roughly three-quarters full keeps every operation to a handful of probes, which is the constant in "constant time". Let the table fill up and the constant quietly becomes enormous.
The resize looks like it should ruin the O(1) claim, since rehashing every entry is O(n). It does not, because of doubling. Each resize doubles the capacity, so between one resize and the next you insert as many keys as the whole table already held. Spread the one-time O(n) rehash cost across all those cheap inserts and it averages out to a constant per insert. This is amortized analysis, and it is the same argument that makes a growable array's append O(1). Doubling is what makes it work: grow by a fixed amount instead and you would resize far too often, and the average would climb to O(n).
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, and why isn't it anywhere near 1,000,000 × 1,000,000?
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 total — only twice the final size, not a multiple of it. The table doubles roughly 16 times to go from 16 slots to over a million (2^20 ≈ 1,048,576), and each resize copies only the entries present at that moment: 16, then 32, then 64, and so on. That series (16 + 32 + ... + 1,000,000) sums to just under 2,000,000 — a doubling series always sums to about twice its last term. Divide 2,000,000 copies across 1,000,000 inserts and each insert pays about 2 extra copies on average: a constant. That is amortized O(1).
Variants worth knowing
"Hash table" names a family, and the biggest split is how collisions are handled. This page built open addressing (all entries live in the array itself). The other classic scheme is separate chaining.
- Separate chaining — each bucket holds a small linked list (or, in Java 8+, a list that becomes a red-black tree once it grows past 8 entries). Colliding keys go into the same bucket's list. It tolerates high load factors gracefully and makes deletion trivial (no tombstones), but it costs a pointer chase per collision and scatters entries across memory, hurting cache locality.
- Quadratic probing and double hashing — open-addressing schemes that probe with a growing gap (1, 4, 9, ...) or a second hash instead of always +1. They avoid the long contiguous runs that linear probing builds up (primary clustering), at the cost of worse cache behavior than a linear walk.
- Robin Hood hashing — an open-addressing tweak where, on a collision, the entry that has traveled further from its home bucket gets to stay, and the closer one is bumped along. This evens out probe distances and makes lookups more predictable, which is why several modern hash tables use it.
- Cuckoo hashing — uses two hash functions and two possible buckets per key, guaranteeing worst-case O(1) lookup (check just two slots). Inserts can cascade as keys kick each other out of their slots, occasionally forcing a rehash, but reads are rock-solid.
- Swiss tables — a modern open-addressing design (Google's Abseil, Rust's hashbrown, and Go 1.24's map) that stores a one-byte fingerprint per slot and scans a group of slots at once with SIMD instructions. It keeps open addressing's cache-friendliness while cutting the probe cost dramatically.
Trade-offs and when to reach for one
A hash table is the default choice whenever you need to look things up by an exact key and you do not care about order. That covers an enormous amount of everyday code, which is why it is the most-used data structure after the array. It is the wrong choice the moment order or ranges enter the picture.
- For: exact-key lookup, insert, and delete at O(1) average — caches, dictionaries, symbol tables, de-duplication (a hash set), grouping and counting, and joining two datasets on a key.
- Against (ordered queries): a hash table stores keys in a scrambled order, so it cannot answer "the smallest key", "keys between 10 and 20", or "the next key after this one". Those need a balanced tree, a B-tree, or a skip list, which keep keys sorted at the cost of O(log n) operations.
- Against (worst-case guarantees): the O(1) is on average. A safety-critical or adversarial setting that cannot tolerate an occasional slow operation should prefer a structure with a hard bound, or a hash table hardened against worst cases (a randomized/keyed hash, or cuckoo hashing for O(1) worst-case reads).
Hash table vs balanced BST vs skip list vs array
| 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 |
Read the table by its first two rows against its third. The hash table wins outright on raw lookup and update speed, and loses outright on anything that needs order. That is the entire choice: if you never ask an ordered question, the hash table is faster; the moment you do, you pay O(log n) for a tree or skip list to get sorted keys.
Failure modes: bad hashes, clustering, and hash flooding
The worst case is real and it is always the same shape: too many keys land in too few buckets, probe chains grow long, and O(1) degrades toward O(n). What differs is the cause.
- A weak hash function — if the hash clusters keys instead of spreading them, some buckets overflow while others stay empty, and the average operation slows even at a low load factor. Using the wrong bits (for example, masking a hash whose low bits barely change) has the same effect.
- Primary clustering — linear probing's own tendency to build long contiguous runs of occupied slots, because each collision extends a run and makes the next collision more likely. It is the reason quadratic probing, double hashing, and Robin Hood hashing exist.
- Tombstone buildup — under a heavy delete workload, a table fills with tombstones that lookups must still probe past, so operations slow even though the live-entry count is low. The cure is to rehash the table (into a clean array) once tombstones pass a threshold, which also clears them out.
- Hash flooding (HashDoS) — if an attacker knows your hash function, they can craft thousands of keys that all collide into one bucket, turning every lookup into an O(n) scan and stalling the server. The defense is a randomized, keyed hash (such as SipHash, now the default in Python, Rust, and others) so the collision pattern is unpredictable per process.
Where hash tables run in the wild
- Python's dict and set — open addressing, capacity a power of two starting at 8, resized when the table passes two-thirds full. Since dictionaries back every object's attributes and every namespace, this is one of the most-executed hash tables on Earth. Python also uses SipHash for string keys to resist hash flooding.
- Java's HashMap — separate chaining with a default capacity of 16 and a load factor of 0.75, so it doubles to 32 after the 12th entry. Since Java 8, a bucket whose chain grows past 8 entries converts to a red-black tree, bounding the worst case at O(log n) instead of O(n).
- Go's map — historically separate chaining with 8-entry buckets and overflow buckets, growing near a load factor of 6.5 entries per bucket. Go 1.24 replaced it with a Swiss Table (open addressing with SIMD group scans), growing at 7/8 occupancy — Datadog reported it cut their map memory by hundreds of gigabytes.
- Redis — its top-level keyspace is a hash table, and it rehashes incrementally: rather than stop the world to double the table, it keeps the old and new tables side by side and migrates a few buckets on each operation, so no single command pays the full O(n) cost.
- Databases and compilers — hash joins build an in-memory hash table on one table's join key to match rows in a single pass, and compilers use hash tables as symbol tables to resolve every identifier. Both lean on O(1) exact-key lookup.
Common misconceptions & gotchas
Why can't I just empty a slot when I delete a key?
Because emptying it can break a probe chain that runs through it. If a later key was placed by probing past the deleted slot, a lookup for that key would hit the now-empty slot, conclude the key is absent, and stop early. Open addressing deletes by leaving a tombstone — a marker that lookups probe past and inserts may reuse — so the chain stays intact.
Why does the whole table have to be rehashed on a resize? Can't it copy the slots over?
No, because a key's bucket is hash % capacity, and the resize changes the capacity. A key that was 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 by recomputing its bucket against the new size.
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, which is the case you design for and almost always get. It degrades to O(n) in the worst case — every key colliding into one chain — from a bad hash, an adversarial input, or a table left too full. Java 8 softens the worst case to O(log n) by treeifying long chains.
What happens if I mutate a key after inserting it?
You lose it. The key was placed in the bucket computed from its hash at insert time. Mutate the key and its hash changes, so a lookup now computes a different bucket and never finds it, even though it is still sitting in the table. This is why hash keys should be immutable — strings, numbers, frozen tuples — never a mutable object whose contents (and hash) can change.
Why is the capacity almost always a power of two?
So that hash % capacity can be computed as a fast bitwise AND with (capacity − 1) instead of a slow division. Doubling on resize keeps it a power of two. The trade-off is that the mask only uses the hash's low bits, so implementations mix the high bits down first to avoid clustering.
QuizA hash table with open addressing is at a load factor of 0.95 and lookups have become very slow. What is the single most effective fix?
- Switch to a slower but stronger cryptographic hash function
- Resize the table larger, dropping the load factor back toward 0.5
- Delete some keys to make room
- Add more probing attempts before giving up
Show answer
Resize the table larger, dropping the load factor back toward 0.5 — At α = 0.95, an unsuccessful search averages about 200 probes; at α = 0.5 it averages about 2.5. The cost is driven almost entirely by how full the table is, so growing the array and rehashing (which drops α) restores O(1). A cryptographic hash is slower and unnecessary; deleting keys leaves tombstones that still count as occupancy; and more probing attempts just walk the same long chains.
In an interview
Lead with the shape: a hash table is an array plus a hash function, giving O(1) average lookup, insert, and delete by hashing each key to a bucket. Then name the two things every follow-up probes — collisions and resizing. Collisions are handled by open addressing (probe to the next slot) or separate chaining (a list per bucket). Resizing doubles the array and rehashes every entry when the load factor crosses a threshold, and doubling is what makes that amortized O(1).
Be ready for the sharp questions. Why not just use an array? Because real keys are not small integers. Why can't you null out a deleted slot? Because it breaks probe chains, so you tombstone instead. Why rehash the whole table? Because the bucket depends on the capacity, which changed. Why doubling and not a fixed increment? Because only doubling makes the amortized cost constant. And the classic: is it really O(1)? On average yes, worst case O(n), which is why a good hash and a bounded load factor matter.
The trade-off question is the one that separates candidates: when would you not use a hash table? When you need ordered operations — ranges, minimums, or sorted iteration — because a hash table scrambles key order. Then open the simulator: PUT keys until two collide and watch the probe, then PUT one more to cross the threshold and watch every entry rehash into the doubled table.
References & further reading
- Wikipedia — Hash table — overview: hashing, collision resolution, load factor, and dynamic resizing
- 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
- Abseil — Swiss Tables design notes — modern open addressing with per-slot fingerprints and SIMD group probing
- 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
- FNV hash — Fowler/Noll/Vo reference — the fast, non-cryptographic string hash the simulator uses
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.