Hash Tables — O(1) Lookup With Collision Resolution

What the O(1) actually promises

The constant-time claim is not a guarantee about any single operation. It is an expected bound, averaged over the random choice of hash function, and for insertion it is additionally amortized, averaged over a sequence that includes the resize. Three assumptions hold it up. First, the hash spreads keys close to uniformly over the buckets. Second, the load factor stays bounded away from the point where probe sequences blow up. Third, comparing two keys is itself O(1) — which is false for long strings, where a lookup that reaches the comparison stage pays a memcmp proportional to the key length.

Break the first assumption and a chained table degrades to a linked list: O(n) per lookup, and it does so silently, because nothing in the API reports it. Break the second and open addressing degrades far faster than chaining does — the arithmetic below shows a 50x jump in miss cost between load factors of 0.75 and 0.90. Only the third failure is usually visible in a profile.

There is a second, quieter problem with the label. O(1) counts operations, not nanoseconds, and on modern hardware a single probe that misses cache and the TLB costs on the order of 100 ns while three probes inside one already-resident cache line cost a couple of nanoseconds. A table with a worse probe count can be several times faster. Asymptotics choose the algorithm; the memory hierarchy chooses the implementation.

The hash function and the bucket index are two different things

A hash function produces a wide value — 32 or 64 bits. A table has m buckets. Something must reduce one to the other, and that reduction is where more tables go wrong than in the hash itself. Two reducers dominate. h % m with m prime mixes every input bit into the result and survives badly structured hashes, but a 64-bit integer division has roughly 20 to 40 cycles of latency and sits on the critical path of every operation. h & (m - 1) with m a power of two costs one cycle and looks at nothing but the low bits.

Masking is therefore only as good as the low bits of the hash. CPython makes this easy to see: hash(i) is the identity for small integers, so masking maps every multiple of 16 onto the same slot.

>>> [hash(i) & 15 for i in range(0, 160, 16)]   # every multiple of 16
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]                  # ... lands in bucket 0
>>> [hash(i) & 15 for i in range(8)]
[0, 1, 2, 3, 4, 5, 6, 7]
>>> hash(-1), hash(-2)                          # -1 is CPython's error sentinel
(-2, -2)

Implementations answer this differently. Java's HashMap folds the high bits down before masking with h ^ (h >>> 16), cheap insurance against hashes like String.hashCode whose avalanche in the upper half is poor. CPython leaves the home slot as the raw masked hash but derives the rest of the probe sequence from the full width via a perturb register, so structured keys collide on the first slot and diverge immediately after. Fibonacci hashing takes a third route: multiply by 2**64 / phi and read the top bits, one multiply that pushes every input bit upward.

Collisions are not an edge case: the birthday arithmetic

Two different events get called collisions and they have wildly different probabilities. A hash collision is two keys producing the same wide hash value. A bucket collision is two keys landing in the same slot after reduction. Since m is minuscule compared to 2**64, bucket collisions are the ones that govern performance, and they are not rare — they are the normal case.

Throw n keys uniformly into m buckets and the expected number of colliding pairs is about n**2 / 2m. A 50 percent chance of at least one collision arrives at roughly 1.18 * sqrt(m) keys — 77 thousand keys against a 32-bit space, about 5.1 billion against a 64-bit one. Two design consequences follow. Storing the full hash alongside each entry costs 4 or 8 bytes and turns almost every negative comparison into an integer test instead of a string compare, which is why essentially every serious implementation does it. And because a 64-bit collision is so improbable, a lookup that matches on the stored hash still must compare the keys: the improbable is not the impossible, and a map that skips the check is a correctness bug waiting for scale.

Distribution matters as much as the mean. With n = m keys under uniform hashing, the longest chain is Theta(log n / log log n) — about five or six entries at a million keys. Your p50 lookup is fine. Your p99.9 lookup is walking that chain.

Three physical layouts, one interface

Every hash table exposes the same three operations, and implementations differ almost entirely in where the entries physically sit. Separate chaining keeps an array of pointers and hangs entries off it in linked lists or small vectors. Open addressing stores entries in the array itself and resolves a conflict by moving along a probe sequence until a free slot appears. Metadata-first designs — SwissTable and its descendants — store entries inline like open addressing but add a compact one-byte-per-slot control array that can be scanned sixteen slots at a time.

Reading the diagram as a cost model: chaining pays one dependent load per link, and dependent loads cannot be overlapped by the processor because the address of the next one is the result of the previous. Open addressing walks a contiguous run, which the hardware prefetcher handles almost for free, but a run merges with its neighbors as the table fills. Metadata-first spends one byte per slot to make the common negative lookup touch only the small control array and never the wide key and value slots — the decisive advantage when entries are large.

Nothing here is a strict ordering. Chaining wins when values are large or when references into the table must stay valid; open addressing wins on small entries; metadata-first wins on lookup-heavy workloads with big values.

Separate chaining, and why Java grows trees inside buckets

Chaining degrades gracefully. Write a for the load factor, live entries divided by buckets. An unsuccessful search examines a entries on average and a successful one about 1 + a/2, both linear in the load factor with a gentle slope — which is why chained tables tolerate a > 1 without drama. There is no clustering to speak of and no tombstone problem, because deletion is just an unlink.

The bill arrives as memory and as pointer chasing. A Java HashMap.Node under compressed oops is a 12-byte object header plus a 4-byte cached hash plus three 4-byte references (key, value, next) — 28 bytes, padded to 32 — before the key and value objects themselves exist. Add the table array slot, roughly 5.3 bytes per entry at the default 0.75 load factor, and a map of a million entries has spent about 37 MB purely on structure. Those nodes are separately allocated, so a chain walk is a walk through wherever the allocator happened to put them.

Java's defaults are worth knowing precisely: initial capacity 16, load factor 0.75, resize by doubling. A bin converts to a red-black tree at TREEIFY_THRESHOLD of 8, but only once the table has at least MIN_TREEIFY_CAPACITY of 64 slots — below that it simply resizes instead — and converts back at 6. The JDK source justifies the 8 with a Poisson model: at the default threshold the mean bin occupancy is about 0.5, which puts the probability of a bin reaching eight entries near 6e-8. Tree bins are therefore not a performance feature. They are a backstop against adversarial keys, and they cap the worst case at O(log n).

Open addressing: the probe-count table worth memorizing

Knuth's analysis gives closed forms, and they are worth carrying around because they explain design choices that otherwise look arbitrary. For linear probing, an unsuccessful search costs about (1 + 1/(1-a)**2) / 2 probes and a successful one about (1 + 1/(1-a)) / 2. For uniform probing — the idealization double hashing approximates — the same quantities are 1/(1-a) and ln(1/(1-a)) / a.

The linear-probing miss column is the whole story of primary clustering. A run of occupied slots is a target that grows: any key hashing anywhere inside it extends it, so long runs attract more keys and merge with their neighbours. That is quadratic blowup in 1/(1-a) rather than linear, and it is why every open-addressed table needs a hard resize threshold well before full.

And yet linear probing keeps winning benchmarks, because the table counts probes and the machine counts cache lines. Eight sequential probes touch one or two lines the prefetcher has already fetched; four double-hashing probes are four independent random accesses, each potentially a DRAM round trip. Quadratic probing splits the difference — with triangular offsets i(i+1)/2 it visits every slot of a power-of-two table, keeping the early probes local while breaking up long runs. Double hashing needs its step coprime to m, which on a power-of-two table means forcing the step odd. One caveat on the formulas: they assume uniform hashing. Linear probing provably needs 5-independent hashing to hit these bounds (Pagh, Pagh and Ruzic, 2007), and Patrascu and Thorup later showed that a merely 2-independent family such as plain multiply-shift can push it to Theta(log n).

Deletion is where open addressing gets hard

Chaining deletes in one unlink. Open addressing cannot simply blank a slot, because the empty slot is the terminator for every probe sequence that ran through it — clearing it orphans every entry further along the run. The usual fix is a tombstone: a third slot state meaning occupied-for-probing, free-for-insertion.

Tombstones work and they leak. A lookup cannot stop at one, so the effective load factor for search purposes is (live + tombstones) / m even when the live count is flat. The failure mode this produces in production is specific and worth naming: a steady-state workload with equal inserts and deletes never grows used, so a resize trigger keyed on used alone never fires, and the table drifts toward every slot being a tombstone with lookups degrading into full scans. Drive the resize decision on live entries plus tombstones, and rehash in place — same capacity, tombstones dropped — when the live count has not actually grown.

Linear probing has an alternative that avoids tombstones entirely: backward-shift deletion, Knuth's Algorithm 6.4R. After clearing the slot, walk forward and pull back any entry whose home slot is not inside the gap you have opened. It does not generalize to quadratic or double hashing, where the probe sequence is not a contiguous run. Note the loop below continues past entries that cannot move rather than stopping at the first one — stopping early is the classic bug, and it silently orphans entries deeper in the cluster.

class LinearProbed:
    """Open addressing, linear probing, backward-shift deletion (Knuth 6.4R)."""

    def __init__(self, cap=8):
        self.mask = cap - 1
        self.slots = [None] * cap            # (hash, key, value) or None
        self.used = 0

    def _home(self, h):
        return h & self.mask                 # cap is a power of two

    def _find(self, key):
        h = hash(key)
        i = self._home(h)
        while self.slots[i] is not None:
            sh, sk, _ = self.slots[i]
            if sh == h and sk == key:
                return h, i, True
            i = (i + 1) & self.mask
        return h, i, False                   # i is the first free slot

    def get(self, key):
        _, i, found = self._find(key)
        if not found:
            raise KeyError(key)
        return self.slots[i][2]

    def put(self, key, value):
        if (self.used + 1) * 4 > len(self.slots) * 3:    # hold alpha at or below 0.75
            self._grow()
        h, i, found = self._find(key)
        self.slots[i] = (h, key, value)
        if not found:
            self.used += 1

    def delete(self, key):
        _, i, found = self._find(key)
        if not found:
            raise KeyError(key)
        self.slots[i] = None
        self.used -= 1
        j = i
        while True:                          # pull the cluster back, leave no tombstone
            j = (j + 1) & self.mask
            if self.slots[j] is None:
                return
            home = self._home(self.slots[j][0])
            if ((j - home) & self.mask) >= ((j - i) & self.mask):
                self.slots[i], self.slots[j] = self.slots[j], None
                i = j

    def _grow(self):
        old, self.slots = self.slots, [None] * (len(self.slots) * 2)
        self.mask, self.used = len(self.slots) - 1, 0
        for e in old:
            if e is not None:
                self.put(e[1], e[2])

Robin Hood hashing reduces variance, not the mean

Robin Hood hashing is open addressing with one rule added at insert: when the incoming key has travelled further from its home slot than the entry already sitting there, evict the incumbent and continue carrying it. Rich slots give to poor ones.

It is commonly described as minimizing the worst-case probe length, and that is the wrong summary. For a fixed hash function and a fixed set of occupied slots, the total displacement summed over all entries is invariant — rearranging who sits where inside a cluster cannot change how many probes the whole table needs. Robin Hood does not improve the average lookup at all. What it does is collapse the variance: it produces the arrangement minimizing displacement variance among those reachable, and the maximum displacement falls to O(log n) with high probability instead of the much longer tail plain linear probing tolerates. Your p50 does not move; your p99.9 improves dramatically.

The invariant buys a second thing, which is arguably the bigger win. Because displacements along a run are non-decreasing, a search can abandon early: if the probe has travelled further than the entry currently in the slot, the key cannot be in the table, and an unsuccessful lookup returns without scanning to the end of the cluster. Backward-shift deletion pairs naturally with the same invariant. Rust's standard HashMap was Robin Hood until version 1.36 in 2019, when it adopted hashbrown's SwissTable implementation.

SwissTable: probe the metadata, not the slots

The SwissTable design, from Abseil in 2017, starts from the observation that in a lookup-heavy workload most probes are negative and most negative probes should never need to read a key at all. It splits the hash: the top 57 bits (H1) choose a group of 16 slots, the low 7 bits (H2) are stored in a separate one-byte control word per slot. Control bytes live in their own array, so one 64-byte cache line covers four groups of metadata.

A lookup loads a group's 16 control bytes into an SSE2 register, compares them against a broadcast H2 with a single _mm_cmpeq_epi8, and extracts a 16-bit candidate mask with _mm_movemask_epi8 — roughly four instructions to filter sixteen slots. Only slots whose bit is set get their key read. H2 is 7 bits, so a non-matching slot survives the filter with probability 1/128; a miss almost always touches metadata only. The encoding also makes the control byte carry state: 0x80 is empty, 0xFE deleted, and any value with the high bit clear is full and holds H2, so asking whether a group has room is another mask test on the same loaded register.

Groups are probed quadratically, and because a group is 16 slots wide the table runs to a maximum load factor of 7/8 rather than the 0.75 typical of scalar open addressing — with one byte per slot of metadata overhead, which is far less than the pointer per entry that chaining costs. Deletion writes the deleted byte, and it can be downgraded back to empty when the group it sits in was never full, which keeps tombstones from accumulating in sparse regions. The design has spread: Abseil, Rust's hashbrown and therefore the Rust standard library, and Go's built-in map since Go 1.24.

Resizing: amortized O(1) hides a tail-latency spike

Doubling on resize is what makes insertion amortized O(1): each entry is copied a constant number of times across the table's life because the work between resizes doubles along with the cost. The amortization is real, and it is also a statement about totals, not about any individual call. One unlucky put at ten million entries allocates a fresh array twice the size, walks every live entry into it, and holds both arrays live for the duration — a multi-hundred-megabyte allocation and a stall you will see in a latency histogram long before you see it in a throughput number.

Three mitigations, in increasing order of effort. Presize when you know the count: new HashMap<>((int)(n / 0.75f) + 1), make(map[K]V, n), reserve(n). This is the highest-value line of code in most hot loops and it is usually missing. Rehash incrementally: Redis keeps two tables during a resize and migrates a bucket or two per command, so no single client pays the full copy. Evacuate on touch: Go's pre-Swiss map moved one or two old buckets per write, spreading the same work across the operations causing it.

Two details reward attention. Because Java's capacity is a power of two and the index is (n-1) & hash, doubling splits each bin into exactly two — the entries with hash & oldCap zero stay, the rest move to index + oldCap — so a resize never recomputes a hash. And growth need not track capacity: CPython sizes a new dict at roughly three times the number of live entries, which means a dict that has had heavy deletion actually shrinks at its next resize rather than carrying dead capacity forever.

Adversarial keys: hash flooding and the defenses

In December 2011, Klink and Wälde demonstrated at 28C3 that a few hundred kilobytes of POST body containing deliberately colliding parameter names could pin a CPU for minutes across PHP, Java, Ruby, Python and ASP.NET. The mechanism is exactly the failure of assumption one: every mainstream language parsed form parameters into a hash table keyed by a deterministic, published, unkeyed hash function on attacker-controlled strings. Collapse n keys into one bucket and an O(n) insert loop becomes O(n**2).

The defenses, with their limits. Seed randomization — Python's PYTHONHASHSEED, enabled by default since 3.3 — makes the mapping unpredictable per process, but a weak mixer can leak its seed to an attacker who can observe timing, which is why CPython moved to SipHash-2-4 in 3.4 and SipHash-1-3 in 3.11. A keyed PRF is the actual fix for untrusted keys, at a real cost of perhaps one to two cycles per byte versus a non-cryptographic mixer. Rust makes that trade-off explicit: SipHash-1-3 is the default hasher and the fast unkeyed alternatives are opt-in, so the safe path is the one you get by not thinking. Bounding the worst case is Java's route — String.hashCode is specified in the Javadoc and cannot be changed, so instead long bins become red-black trees, capping the attack at O(log n) per operation.

Two caveats that bite in practice. Randomization is worthless if the hash escapes the process — anything that persists bucket order, shards on the raw hash, or exposes iteration order hands the attacker back what randomization took away. And per-process seeding makes iteration order differ between runs, which is a feature for security and a steady source of flaky tests for anyone who assumed otherwise.

The variants worth knowing, and what each one buys

Cuckoo hashing (Pagh and Rodler, 2001) gives what plain hashing cannot: a worst-case bound on lookup. Each key lives at one of two positions, so a get is at most two probes regardless of load. The cost moves to insert, which may cascade evictions and occasionally fail and rebuild. The textbook two-table, one-slot form stalls near a load factor of 0.5; two hashes over buckets of four slots reach past 0.95, which is the configuration real systems use.

Hopscotch hashing (Herlihy, Shavit and Tzafrir, 2008) guarantees every key sits within a neighborhood of H slots of its home — H is typically 32, one or two cache lines — by hopping incumbent entries backward to open a nearby slot. Lookup becomes a bounded, cache-resident scan, and the bound is what makes concurrent variants tractable.

Perfect hashing applies when the key set is static and known. The FKS construction (Fredman, Komlós and Szemerédi, 1984) uses two levels, a top-level hash into buckets and a per-bucket collision-free hash, to reach worst-case O(1) lookup in O(n) space. Minimal perfect hashing packs n keys into exactly n slots; the information-theoretic floor is log2(e), about 1.44 bits per key, and modern constructions such as CHD, BBHash and RecSplit land within a modest factor of it. Compiler keyword tables and read-only indexes are the natural fit; anything mutable is not.

Universal hashing (Carter and Wegman, 1979) is the machinery underneath every expected-time claim on this page. A family H is universal when a randomly chosen member collides any fixed pair with probability at most 1/m; pick one at construction and the expectation is over your coin flips, not over the adversary's keys. Multiply-shift, (a*x) >> (w - M) with random odd a, is the one-multiply practical default, strictly 2-approximately-universal at 2/m rather than 1/m. Polynomial and rolling hashes compute sum(s[i] * p**i) mod q and update in O(1) as a window slides, which is what makes Rabin-Karp linear — fast, but unkeyed and therefore not adversary-safe. Zobrist hashing XORs a random word per (piece, square) so a chess move updates the key in two XORs, which is how transposition tables stay cheap.

Choosing a table for a real workload

Start from the entry size. Small, movable, trivially copyable entries belong in a SwissTable-style open-addressed map running near 7/8 — the metadata filter and the contiguous layout are strictly better than a pointer per entry. Large values, or values whose addresses must stay stable across insertions, push you to chaining or a node-based map: C++ guarantees reference stability for unordered_map and explicitly does not for the flat variants, and a Robin Hood shift moving 200-byte values around is a real cost, not a theoretical one.

Then the key provenance. Keys from outside the trust boundary get a keyed hash, no exceptions, plus a cap on how many of them a single request may create — hashing alone does not stop unbounded memory growth. Keys fixed at build time get a minimal perfect hash and a flat array, which removes probing entirely. Keys arriving concurrently need either lock striping or a purpose-built concurrent map; note that the resize is the part that serializes, so the presizing advice matters twice as much under contention.

Finally, measure the right things. Hit ratio and average probe length will both look healthy while a table is failing at the tail. Instrument the maximum probe length, the count of tombstones relative to live entries, and the load factor at the moment of your p99 lookup. Those three numbers distinguish a table that is genuinely O(1) from one that has been quietly linear for a week.