The idea: two ways to handle a collision
A hash table turns a key into an array index, its home: here h(k) = k mod m with m = 11. Two keys with the same home collide, and every hash table needs a rule for that. This page puts the same keys into two tables at once. Separate chaining (left) hangs a linked list off each slot. Linear probing (right), the simplest kind of open addressing, keeps every key in the array itself and, on a collision, tries the next slot.
One Step moves both tables by one probe. A probe is one place looked at: chaining reads the bucket and then each node it compares; linear probing reads each slot. The scoreboard under each table also counts cache lines, the 64-byte blocks the CPU actually loads: 8 slots or bucket pointers share one line, but every chain node is a separate allocation somewhere else in memory, so each node costs one more line.
Separate chaining
Each of the m slots is a bucket pointer to a linked list. Insert walks the list (to reject a duplicate, as Java's HashMap does) and appends the new node at the end. Find walks until it meets the key or the end. Delete unlinks one node. A collision never touches another bucket, so a chain is on average only α = n / m nodes long, and the table keeps working even with more keys than slots. The price is memory and pointer chasing: one pointer per slot plus a key and a next pointer per node, scattered over the heap.
Linear probing
The table is one array of keys. To insert k, look at slot h(k), then h(k) + 1, h(k) + 2, … (wrapping around) until a free slot. Find walks the same path and stops at the key or at an empty slot, because an insert would have stopped there too. Nothing is allocated per key, and the probes walk forward through neighbouring slots, usually in the same cache line. At low load that makes linear probing the faster table in practice (Demo: load 0.5, probing reads fewer cache lines: 18 probes and 8 cache lines against chaining's 20 and 20).
Load factor and clustering
The load factor α = n / m decides how much each table pays. Chains grow slowly with α. Linear probing suffers from primary clustering: used slots form runs, a key that lands anywhere in a run is pushed to its end, and the run grows by one, so long runs grow fastest and neighbouring runs merge. A key whose home no other key uses still pays if a neighbour's run has spilled over its home (Demo: primary clustering: keys 2 and 3 cost 1 probe each in chaining and 3 each in probing). Knuth's classic estimates show how sharply it turns:
At α = 0.9 a miss in linear probing may walk almost the whole table (Demo: load 0.9, probe runs blow up: looking up the missing key 33 takes 11 probes against chaining's 4). Note that probing still reads fewer cache lines in that demo (13 against 19): walking an array is cheap, so long runs hurt less than the probe counts suggest, until they get really long.
Deleting: tombstones
Chaining deletes by unlinking a node. Linear probing cannot just empty the slot: a later key may have walked past it, and an empty slot would now stop the search for that key too early. So the slot gets a tombstone (DEL). Find walks past tombstones; insert may reuse the first one it passed (Demo: delete leaves a tombstone: 34 goes into the old slot of 12).
Tombstones are not free: they still count as used slots for every search, so a table with many deletes gets slow even when it holds few keys. They disappear only when the table is rebuilt.
Resizing
Both tables keep α low by growing: allocate a bigger array and insert every key again, because a key's home k mod m changes with m. Each key costs one insert, once, so the cost spread over all inserts stays constant. Java's HashMap (chaining) doubles at α = 0.75; open-addressing tables usually grow earlier, around 0.5 to 0.7, and the rebuild also drops every tombstone (Demo: resize to m = 23: the miss for 33 falls from 9 probes to 1).
When to pick which
| Separate chaining | Linear probing | |
|---|---|---|
| Memory per key | key + next pointer + allocation, plus one pointer per slot | just the slot |
| Cache behaviour | one miss per node visited | probes stay in neighbouring slots |
| High load (α near 1) | degrades gently; α > 1 still works | clusters grow, misses explode; α must stay below 1 |
| Delete | unlink the node | tombstone, cleaned up on rebuild |
| Bad hash function | long chains (Java turns a chain of 8 into a tree) | one huge cluster |
| Used in | Java HashMap, C++ std::unordered_map | Python dict (another probe order), Rust and Abseil Swiss tables, Go maps since Go 1.24 |
Rule of thumb: linear probing when keys are small, the load stays moderate and lookups dominate; chaining when entries are large, deletes are frequent, or the load factor can't be controlled. See also Open Hash Tables and Closed Hash Tables for each table on its own, and How Java's HashMap Works for a real chaining table.
See also Cuckoo Hashing, where every key has only two possible slots, so a lookup takes at most 2 probes even in the worst case.
What the page leaves out
Keys are small integers and the hash is k mod m, with no hash-code mixing. The cache-line count is a simple model (8 entries per line, every chain node in its own line); real allocators sometimes place nodes close together. Other open-addressing schemes are left out: quadratic probing and double hashing (they avoid primary clustering), Robin Hood hashing, cuckoo hashing and SIMD Swiss tables. So are automatic resizing at a threshold, incremental rehashing (Redis), concurrent tables and keys that are larger than a pointer.