Hash Tables & Collision Strategies

A hash table is an array plus a function that turns a key into an index into it. Everything interesting follows from the fact that the function is not injective: two keys land on one slot, and the collision strategy — where the loser goes, and how you find it again — is what separates a textbook table from absl::flat_hash_map. The classical analysis is about probe counts; the modern designs are about cache lines and SIMD, and those two views disagree about which strategy wins.

From key to slot #

Two distinct steps hide behind "hashing a key", and conflating them is the most common source of bad tables.

1. Hash — map the key to a machine word, $h = H(k)$. The requirement is avalanche: every input bit should flip roughly half the output bits, so that structured keys (sequential ids, aligned pointers, strings with a common prefix) do not produce structured hashes.
2. Reduce — map that word onto $[0, m)$ where $m$ is the table's capacity.

The hash function does not have to be cryptographic — see hash flooding below for what it does have to be.

Load factor and the probe-count laws #

The load factor is $\alpha = n/m$: entries divided by slots. Every classical cost result is a function of $\alpha$ alone, not of $n$ — this is why hash tables are $O(1)$ amortised only if you resize to hold $\alpha$ below a bound.

Under the idealised uniform-hashing model (Knuth's analysis), with $\alpha < 1$:

$$\text{linear probing:}\quad C_{\text{hit}} \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right), \qquad C_{\text{miss}} \approx \frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$$

$$\text{uniform (double) hashing:}\quad C_{\text{hit}} \approx \frac{1}{\alpha}\ln\frac{1}{1-\alpha}, \qquad C_{\text{miss}} \approx \frac{1}{1-\alpha}$$

$$\text{separate chaining:}\quad C_{\text{hit}} \approx 1 + \frac{\alpha}{2}, \qquad C_{\text{miss}} \approx \alpha$$

Two things to read off this table. First, the miss column is the one that matters: negative lookups (contains, insert-if-absent, join probes) are the common case in real workloads, and linear probing's $(1-\alpha)^{-2}$ blows up long before the hit cost does. Second, chaining's numbers look untouchable — and they are, as probe counts. They are also close to meaningless on real hardware, which is the subject of the section after next.

The collision strategies #

Separate chaining #

Each bucket holds a list (or, past a threshold, a tree). Simple, tolerates $\alpha > 1$, gives stable addresses, and deletion is trivial. The cost is one allocation and one pointer indirection per entry: a lookup touches the bucket array (one miss), then the node (another miss), then possibly more nodes. That is the worst memory access pattern a modern CPU can be handed — see CPU caches.

Java's HashMap is chained with a defensive twist: since JDK 8, a bin whose list exceeds TREEIFY_THRESHOLD = 8 converts to a red-black tree, provided the table has at least MIN_TREEIFY_CAPACITY = 64 slots (below that it just resizes); it untrees below 6. Default load factor is 0.75. This turns the adversarial worst case from $O(n)$ into $O(\log n)$ per bucket.

Open addressing: linear, quadratic, double #

Everything lives in the slot array. On collision you walk a probe sequence:

• Linear — $s_i = (h + i) \bmod m$. One cache line typically covers several slots, so the first handful of probes are free. Suffers primary clustering.
• Quadratic — $s_i = (h + c_1 i + c_2 i^2) \bmod m$. Kills primary clustering but keys with the same $h$ still share a sequence (secondary clustering), and you must pick constants that visit every slot — the standard trick is $s_i = (h + i(i+1)/2) \bmod m$ with $m$ a power of two, which is a full permutation.
• Double hashing — $s_i = (h_1 + i \cdot h_2) \bmod m$, with $h_2$ forced odd (power-of-two $m$) or coprime to $m$. Best probe counts of the three, worst locality: every probe is a fresh cache line.

CPython's dict is a variant worth knowing: j = (5*j + 1 + perturb) % m with perturb >>= 5 each step, seeded from the full hash. The perturbation injects high hash bits into the early probes; once it drains to zero the recurrence $j \to 5j+1$ is guaranteed to enumerate every slot of a power-of-two table. CPython keeps $\alpha \le 2/3$, and since 3.6 stores a compact indices array over a dense insertion-ordered entries array — which is why dicts are ordered and why the index array can be 1, 2, 4 or 8 bytes wide depending on size.

Robin Hood #

Store each entry's probe sequence length (PSL) — how far it sits from its ideal slot. On insert, if the key being placed has travelled further than the entry currently occupying the slot, swap them and carry on inserting the evicted (richer) entry. Steal from the rich, give to the poor.

This does not change the mean probe count at all — the sum of displacements is fixed by the occupancy pattern. It collapses the variance, and variance is what kills you: the search can also stop early, because if you reach a slot whose PSL is smaller than your current probe distance, your key cannot be in the table. Devroye, Morin & Viola proved the payoff: for a constant $\alpha < 1$ the longest probe sequence is $\log_2 \log n \pm \Theta(1)$ with probability tending to 1, an exponential improvement over the $\Theta(\log n)$ maximum of first-come-first-served linear probing.

Deletion uses backward shift: slide the following run one slot back, stopping at the first empty slot or PSL-0 entry. No tombstones, so a delete-heavy table does not rot.

Cuckoo hashing #

Two (or $d$) tables with independent hash functions; a key lives in exactly one of its $d$ candidate slots, so lookup is worst-case $O(1)$ — at most $d$ probes, and those probes are independent, so the memory system can issue them in parallel. Insert places the key and, if the slot was occupied, evicts the incumbent to its alternate slot, cascading; on a long cascade (a cycle in the cuckoo graph) it gives up and rehashes.

Pagh & Rodler's original two-function scheme needs $m \ge (2+\delta)n$ — a load factor below 0.5 — for amortised-expected-constant insertion. The thresholds rise sharply with more choices or fatter buckets: three hash functions reach roughly 0.91, and bucketed variants (several slots per bucket, so one cache line per probe) get into the mid-0.90s. This is the structure behind cuckoo filters and most hardware/NIC flow tables, where a hard bound on lookup work matters more than insert throughput.

Why open addressing wins on real hardware #

The probe-count table says chaining is best. Measurements on anything built after about 2005 say otherwise, and the reason is that the classical model counts probes, while the machine charges for cache misses and dependent loads.

• A chained lookup is a pointer chase: the address of the next load is not known until the previous load returns. The out-of-order engine cannot hide that latency, and the prefetcher cannot help because the address is unpredictable. Each link is a potential ~80–100 ns trip to DRAM.
• A linear-probing lookup reads consecutive slots. The first probe pulls a 64-byte line containing several slots; the next few probes are L1 hits, and the prefetcher handles the run boundary. Ten "probes" can cost less than one chained link.
• Chaining also costs memory: a node header plus a pointer per entry, plus allocator overhead, which shrinks the effective cache footprint of the whole table.

Swiss tables: metadata bytes and SIMD probing #

The dominant modern design — Google's Swiss tables (absl::flat_hash_map), Rust's hashbrown (the standard library HashMap since Rust 1.36), and Go's map since Go 1.24 — is open addressing plus a separate array of one metadata byte per slot.

Split the 64-bit hash:

• H1 — the upper ~57 bits, used to choose the starting group.
• H2 — the low 7 bits, stored in the control byte.

Each control byte is either a sentinel (EMPTY, DELETED) or 0b0xxxxxxx holding that slot's H2, with the top bit distinguishing occupied from not. The control bytes for a group of slots are contiguous, sized to a SIMD register: 16 with SSE2 (absl, hashbrown), 8 packed into a 64-bit word for Go and for the portable SWAR fallback.

flowchart LR
  K["key"] --> H["h = hash of key"]
  H --> H1["H1: upper 57 bits"] --> G["group index"]
  H --> H2["H2: low 7 bits"]
  G --> L["load 16 control bytes"]
  H2 --> C["SIMD compare vs 16 bytes"]
  L --> C
  C --> M["match bitmask"]
  M --> E["for each set bit: compare key"]
  M --> Z["no match: any EMPTY byte?"]
  Z -->|yes| N["not present"]
  Z -->|no| G2["next group"] --> L

A lookup is: one load of the control bytes, one broadcast, one _mm_cmpeq_epi8, one _mm_movemask_epi8, and you have a 16-bit mask of candidate slots — in a handful of instructions, with no branches and no key comparisons. Then:

• Any set bit → compare that key. H2 is 7 bits, so a wrong-key candidate survives with probability $\approx 1/128$; in practice you compare only keys that are actually equal.
• Mask empty and the group contains an EMPTY byte → the key is absent, stop. This is what makes negative lookups cheap despite a high load factor.
• Otherwise → probe the next group. hashbrown uses triangular numbers over groups ($+1$ group, then $+2$, $+3$, …), which for a power-of-two group count visits every group exactly once.

Because the control array is ~1 byte per slot, a group scan touches one or two cache lines of metadata for 16 slots, and the payload array is touched only for the (nearly always correct) candidate. That is the whole trick: the expensive object — the key — is only ever touched when it is almost certainly the right one.

The density payoff is direct. Abseil runs flat_hash_map at a maximum load factor of 87.5% (7/8) before doubling, with total footprint about (sizeof(pair<const K,V>) + 1) * bucket_count(). Compare that to the linear-probing miss cost at $\alpha = 0.875$ from the table above — 32.5 slot probes — which is only bearable because 16 of them resolve in one vector instruction.

Deletion mostly avoids tombstones: hashbrown writes DELETED only when the deleted slot sits inside a full run of WIDTH non-empty buckets; otherwise it can mark the slot EMPTY, because the probe sequence through it was already terminated by an adjacent empty slot.

Resizing and rehashing #

Growth is geometric — usually doubling — which makes insertion $O(1)$ amortised by the same argument as a dynamic array: $n$ inserts move $n + n/2 + n/4 + \dots < 2n$ entries in total. Two details bite in practice.

Rehashing is not just copying. Entries must be re-placed by their hash against the new capacity, so it costs a full pass with random writes. If the table stores the hash alongside each entry (many do, precisely for this) you skip re-hashing the keys; if not, you pay the hash function again for every entry. Power-of-two capacities help here: doubling splits each old bucket into exactly two new ones based on one extra hash bit.

The amortised bound is a lie for tail latency. One insert in $n$ stops the world for $O(n)$ work. Systems that care about p99 de-amortise it:

• Redis keeps two tables in its dict and an index rehashidx. Ordinary operations call _dictRehashStep, which migrates one bucket; the background cron calls dictRehashMicroseconds, which migrates in chunks of 100 buckets until a microsecond budget expires. During a rehash, lookups consult ht[0] then ht[1], and inserts go straight to ht[1] so the old table only drains. There is also an empty-bucket visit cap (n*10) so a sparse table cannot make one step scan forever.
• Go 1.24 bounds it structurally instead: a large map is not one table but a directory of independent tables under extendible hashing, each holding at most 1024 entries. Growth splits one 1024-entry table, so the worst-case single insertion is bounded by that, not by the map's size.

Shrinking is the neglected half: a table that grew to 10 M entries and then had 9.99 M deleted usually keeps the big array (Redis is unusual in shrinking: dictShrinkIfNeeded fires when the fill ratio drops to 1:8, or 1:32 when resizing is globally discouraged during a fork). With tombstoning open addressing, deletions that are never compacted leave the table at high effective load with no live entries — an insert-heavy, delete-heavy cache that never resizes can slow to a crawl while reporting a tiny len().

Hash flooding and randomised seeds #

Every average-case bound above assumes the keys are not chosen by someone who knows your hash function. If they are, the adversary sends $n$ keys that all hash to the same bucket, and a table degenerates to a linked list: $n$ insertions cost $\Theta(n^2)$.

1. 2003 Crosby & Wallach, USENIX Security — "algorithmic complexity attacks", demonstrated against Perl's hash and against the Bro IDS.
2. 2011 Klink & Wälde, 28C3 — the same attack applied to every web platform at once. Form POST bodies are parsed into a hash table, and PHP, ASP.NET, Java and Python all used simple non-randomised functions (DJBX33A/DJBX33X and relatives). A single crafted POST at ~70–100 kbit/s of sustained bandwidth kept an Intel i7 core pinned at 100%.
3. 2012 Aumasson & Bernstein publish SipHash, designed specifically for this use: a keyed PRF over short inputs, fast enough to sit in a hash-table hot path.
4. 2014 Python 3.4 makes SipHash-2-4 with a per-process random key the default for str/bytes hashing (PEP 456); Python 3.11 switches the default to the faster SipHash-1-3.
5. 2016 Rust's standard library moves its default hasher from SipHash-2-4 to SipHash-1-3; HashMap keys the hasher randomly per instance.

The mitigation is a secret, per-process (or per-table) random seed folded into the hash, so the attacker cannot compute collisions offline. Three consequences:

• The hash function must be keyed and unpredictable, not collision-resistant in the cryptographic sense. SipHash is a PRF, not a hash in the SHA-2 sense — an attacker who cannot recover the key cannot find colliding inputs, which is all the table needs. A full cryptographic hash would work and would also be needlessly expensive: a table hashes short keys, millions of times per second, and cares about latency on 8-byte inputs.
• Iteration order becomes nondeterministic across runs — the intended side effect. Code that depends on map iteration order breaks, which is why Go deliberately randomises the start of map iteration and why PYTHONHASHSEED=0 exists as an escape hatch for reproducible builds.
• Fast non-keyed hashers (FxHash, wyhash, xxHash, ahash without a random key) are the right choice only when every key is trusted — internal compiler symbols, ids you generated yourself. The moment a key crosses a network boundary, the flooding case is live.

Choosing, concretely #

• General in-memory map, keys you control → an open-addressed SIMD table: absl::flat_hash_map, Rust's HashMap (hashbrown), Go's map since 1.24. Do not reach for std::unordered_map unless you need its address stability.
• Values that must not move → store unique_ptr/Box values in a flat table rather than switching to a node-based container; you keep the flat probe path and pay one indirection only on access.
• Hard bound on lookup work (packet classification, hardware tables, filters) → bucketed cuckoo: exactly $d$ parallel probes, and accept that insertion has a long tail.
• High load factor with deletes, hand-rolled → Robin Hood with backward-shift deletion; it is the simplest scheme that stays sane at $\alpha = 0.9$ and needs no tombstones.
• Keys arrive from the network → keyed hash with a random per-process seed (SipHash-class), or a collision-tolerant bucket structure. Never both a fast unkeyed hash and untrusted keys.
• Approximate membership at a fraction of the memory → you may not want a hash table at all; see probabilistic structures.