Hash tables

Where does a hash table fall off a cliff?

The constraint. If you can compute a position from the key, a lookup needs exactly one dependent fetch. That is the theoretical floor. The price: the computation is a random map, so order is destroyed. Also, by the birthday bound, collisions begin after only about √m insertions into m slots. (With 1,000,000 slots, you expect the first collision after roughly 1,000 keys. The same effect makes two people in a room of 23 likely to share a birthday.) Collisions are not a flaw in your hash function. They are the definition of squeezing a large key space into a small address space.

The dial is load factor, and its cost curve is a hyperbola

The load factor α ("alpha") is the fraction of slots that are full. In linear probing (if the slot is taken, try the next slot, then the next), the expected number of probes is roughly:

½ × (1 + 1/(1 − α)) for a successful lookup (a hit);
½ × (1 + 1/(1 − α)²) for a failed lookup or an insert (a miss).

Worked example

Load factor α	Probes for a hit	Probes for a miss or insert
0.5	½ × (1 + 1/0.5) = ½ × 3 = 1.5	½ × (1 + 1/0.25) = ½ × 5 = 2.5
0.9	½ × (1 + 1/0.1) = ½ × 11 = 5.5	½ × (1 + 1/0.01) = ½ × 101 ≈ 50

RelationshipLinear probing: probes by load factor →

\frac{1}{2} \times (1 + 1/ (1 - α)), \frac{1}{2} \times (1 + 1/ (1 - α)^{2})

$α$: the fraction of slots that are full

hitmiss or insert

Data table

Expected probes by load factor
Load factor α	series	Expected probes
0	hit	1
0.012	hit	1.01
0.024	hit	1.01
0.036	hit	1.02
0.048	hit	1.02
0.059	hit	1.03
0.071	hit	1.04
0.083	hit	1.05
0.095	hit	1.05
0.107	hit	1.06
0.119	hit	1.07
0.131	hit	1.08
0.142	hit	1.08
0.154	hit	1.09
0.166	hit	1.1
0.178	hit	1.11
0.19	hit	1.12
0.202	hit	1.13
0.214	hit	1.14
0.226	hit	1.15
0.237	hit	1.16
0.249	hit	1.17
0.261	hit	1.18
0.273	hit	1.19
0.285	hit	1.2
0.297	hit	1.21
0.309	hit	1.22
0.321	hit	1.24
0.332	hit	1.25
0.344	hit	1.26
0.356	hit	1.28
0.368	hit	1.29
0.38	hit	1.31
0.392	hit	1.32
0.404	hit	1.34
0.416	hit	1.36
0.427	hit	1.37
0.439	hit	1.39
0.451	hit	1.41
0.463	hit	1.43
0.475	hit	1.45
0.487	hit	1.47
0.499	hit	1.5
0.511	hit	1.52
0.522	hit	1.55
0.534	hit	1.57
0.546	hit	1.6
0.558	hit	1.63
0.57	hit	1.66
0.582	hit	1.7
0.594	hit	1.73
0.606	hit	1.77
0.617	hit	1.81
0.629	hit	1.85
0.641	hit	1.89
0.653	hit	1.94
0.665	hit	1.99
0.677	hit	2.05
0.689	hit	2.11
0.701	hit	2.17
0.713	hit	2.24
0.724	hit	2.31
0.736	hit	2.4
0.748	hit	2.49
0.76	hit	2.58
0.772	hit	2.69
0.784	hit	2.81
0.796	hit	2.95
0.807	hit	3.1
0.819	hit	3.27
0.831	hit	3.46
0.843	hit	3.69
0.855	hit	3.95
0.867	hit	4.26
0.879	hit	4.62
0.891	hit	5.07
0.903	hit	5.63
0.914	hit	6.34
0.926	hit	7.28
0.938	hit	8.58
0.95	hit	10.5
0	miss or insert	1
0.012	miss or insert	1.01
0.024	miss or insert	1.02
0.036	miss or insert	1.04
0.048	miss or insert	1.05
0.059	miss or insert	1.07
0.071	miss or insert	1.08
0.083	miss or insert	1.09
0.095	miss or insert	1.11
0.107	miss or insert	1.13
0.119	miss or insert	1.14
0.131	miss or insert	1.16
0.142	miss or insert	1.18
0.154	miss or insert	1.2
0.166	miss or insert	1.22
0.178	miss or insert	1.24
0.19	miss or insert	1.26
0.202	miss or insert	1.28
0.214	miss or insert	1.31
0.226	miss or insert	1.33
0.237	miss or insert	1.36
0.249	miss or insert	1.39
0.261	miss or insert	1.42
0.273	miss or insert	1.45
0.285	miss or insert	1.48
0.297	miss or insert	1.51
0.309	miss or insert	1.55
0.321	miss or insert	1.58
0.332	miss or insert	1.62
0.344	miss or insert	1.66
0.356	miss or insert	1.71
0.368	miss or insert	1.75
0.38	miss or insert	1.8
0.392	miss or insert	1.85
0.404	miss or insert	1.91
0.416	miss or insert	1.96
0.427	miss or insert	2.03
0.439	miss or insert	2.09
0.451	miss or insert	2.16
0.463	miss or insert	2.23
0.475	miss or insert	2.31
0.487	miss or insert	2.4
0.499	miss or insert	2.49
0.511	miss or insert	2.59
0.522	miss or insert	2.69
0.534	miss or insert	2.81
0.546	miss or insert	2.93
0.558	miss or insert	3.06
0.57	miss or insert	3.2
0.582	miss or insert	3.36
0.594	miss or insert	3.53
0.606	miss or insert	3.71
0.617	miss or insert	3.92
0.629	miss or insert	4.14
0.641	miss or insert	4.38
0.653	miss or insert	4.66
0.665	miss or insert	4.96
0.677	miss or insert	5.29
0.689	miss or insert	5.66
0.701	miss or insert	6.08
0.713	miss or insert	6.55
0.724	miss or insert	7.08
0.736	miss or insert	7.69
0.748	miss or insert	8.38
0.76	miss or insert	9.18
0.772	miss or insert	10.1
0.784	miss or insert	11.2
0.796	miss or insert	12.5
0.807	miss or insert	14
0.819	miss or insert	15.8
0.831	miss or insert	18.1
0.843	miss or insert	20.8
0.855	miss or insert	24.3
0.867	miss or insert	28.7
0.879	miss or insert	34.5
0.891	miss or insert	42.3
0.903	miss or insert	53.1
0.914	miss or insert	68.7
0.926	miss or insert	92.4
0.938	miss or insert	131
0.95	miss or insert	200

Principle: Queues explode near full load →

The last ten percent of a hash table costs more than the first ninety.

The shape 1/(1 − α) should look familiar to anyone who has studied queues. 1/(1 − ρ) is the multiplier for waiting time in the simplest queue model (one server, random arrivals, called M/M/1): at 90% utilization, a request waits about 10 times the service time. This is not an analogy. The analysis of clustering in hash tables (due to Knuth) and queueing theory are the same mathematics, because a probe sequence is a queue for a slot. Any resource that is allocated by contention (everybody tries, the unlucky ones retry) rather than by assignment (each user gets a reserved place) costs hyperbolically as it approaches capacity. We call this the Queueing law:

Chaining versus open addressing is a cache argument

Two classic collision strategies:

Chaining: each slot holds a linked list of the keys that landed there.
Open addressing: all keys live in the array itself; on collision you probe other slots (like linear probing above).

Both are O(1) amortized. But chaining follows a pointer on every collision, and a pointer chase is a dependent cache miss: about 80 ns of waiting. Open addressing scans forward inside the same cache line or the next one. This is why every high-performance hash table built in the last decade (Abseil's Swiss tables, Folly's F14) uses open addressing with one byte of metadata per slot, scanned sixteen slots at a time with SIMD (one CPU instruction that compares 16 bytes at once). The cost model is cache lines touched. The comparison count is irrelevant.

Chaining survives where entries are large, where deletion must be trivial, or where you need stable references to values (a pointer to a value that stays valid when the table grows).

# Open addressing with linear probing, minimal version (no deletion, no resize).
def put(table, key, value):
    i = hash(key) % len(table)
    while table[i] is not None and table[i][0] != key:
        i = (i + 1) % len(table)          # next slot: usually the same cache line
    table[i] = (key, value)

def get(table, key):
    i = hash(key) % len(table)
    while table[i] is not None:
        if table[i][0] == key:
            return table[i][1]
        i = (i + 1) % len(table)
    return None                            # an empty slot ends the search

Robin Hood hashing reduces variance, not the mean

Robin Hood hashing does not lower the average probe count at all. It makes probe counts more equal. When a new key collides with an existing key, it compares how far each key is from its ideal slot, and the key that is closer to home (the "rich" key) gives up its slot to the one that is farther (the "poor" key). The mean stays the same. The tail collapses.

In a system with a p99 latency budget, that trade is free. It is a direct instance of the Variance law:

It also gives early termination on negative lookups: because keys are kept in order of distance from home, a search can stop as soon as it meets a key that is closer to home than the search has traveled. This matters more than it sounds, because negative lookups (asking for something that is not there) dominate in any structure that sits behind a filter.

Cuckoo hashing buys a worst-case bound with an unbounded insert

Cuckoo hashing uses two hash functions, so each key has two candidate slots. A lookup needs at most two probes, regardless of load and regardless of an adversary choosing keys. An insert may cascade: the new key evicts the key in its slot, which moves to its other slot and evicts another key, and so on. A cascade can fail outright and force a rehash. Two functions with one slot each saturate near 50% occupancy. With four slots per bucket, occupancy can go beyond 95%, and that is what makes the design practical.

The mechanism underneath is worth extracting because it recurs outside this mechanism. Throw n balls into n bins at random with one hash function: the fullest bin holds Θ(log n / log log n) balls. With two choices (put each ball in the less full of two random bins), the fullest bin holds only Θ(log log n). That is an exponential improvement from one extra choice. It is called the power of two choices, and it also appears in load balancers: pick two servers at random, send the request to the less busy one. Same mechanism, different costume. A single random assignment concentrates badly; the minimum over two random assignments concentrates tightly. This is why it appears anywhere load is spread without a coordinator.

Growth is the problem nobody teaches

Doubling a hash table means rehashing every key: a stop-the-world O(n) pause. In a path with a latency budget, that is unacceptable. The escapes all limit how much of the mapping changes at once:

Incremental rehash with two live tables (Redis): move a few entries per operation from the old table to the new one.
Extendible hashing: a directory of pointers to buckets that doubles, while individual buckets split on their own.
Linear hashing: split one bucket per insert in a fixed rotation, so the table grows smoothly.

These last two are the dynamic hashing on disk methods; the in-memory descriptions above often leave them out, but the pause problem they solve is exactly the one on this page.

The distributed answer to the same problem is consistent hashing. When a server joins a cluster, you want 1/n of the keys to move, not all of them. Consistent hashing is not a distributed-systems invention. It is the rehash problem with the cost counted in network transfers instead of memory writes.

Where hash tables bite in data engineering

Inside a query engine, hash tables are the build side of a hash join, the state of a hash aggregation, and the partitioner of a shuffle (the step that sends each row to the worker that owns its key). In none of these is probe count the main concern. The main concern is footprint per distinct key, because it decides the number of partitions, and the number of partitions decides whether the operator spills (writes its state to disk because memory is full). A hash aggregation that fits in memory and one that spills differ by an order of magnitude, not by a percentage. The structure degrades discontinuously.

The trigger for that discontinuity is almost always skew: hash partitioning assumes keys are independent and nearly uniformly spread. We call this the Independence law:

The party that pays is whichever task received the hot key.