Cuckoo Hashing and Fingerprint Filters

One design choice, giving every element two candidate slots, delivers worst-case O(1) lookups and deletion support at the same time.

Lookups that read only two slots

In a chaining hash table, lookup cost grows with the number of elements hanging off a bucket. Cuckoo hashing nails that upper bound to a constant. It keeps two hash functions h1 and h2 over two arrays T1 and T2, and a key k lives in exactly one of T1[h1(k)] and T2[h2(k)]. A lookup reads two slots, so it is O(1) even in the worst case.

The cost lands on insertion instead. When the target slot is already taken, the new key evicts the resident key and claims the slot. The evicted key moves to its own alternate slot, and if that slot is taken as well, it evicts the key sitting there. The name comes from the cuckoo bird, which pushes other eggs out of a nest it did not build.

insert A -> T1[h1(A)] holds B    => A evicts B
         B -> T2[h2(B)] holds C    => B evicts C
           C -> T1[h1(C)] is empty  => chain ends

When the chain forms a cycle, the insertion never terminates. Implementations therefore cap the number of moves (MaxLoop) and, once the cap is exceeded, rehash the whole table with a fresh pair of hash functions. The probability of hitting a cycle falls exponentially as the load factor drops. In the standard single-slot configuration the load factor threshold sits near 50%, and close to it the expected insertion cost approaches O(n).

What extra hash functions buy

Raising the number of hash functions to d (d ≥ 3) gives each key d candidate slots and pushes the threshold much higher. Whether insertion cost stays constant across that range was an open question for a long time. Work presented at FOCS 2024 (arXiv:2401.14394) proved that random-walk d-ary cuckoo hashing has expected O(1) insertion at any load factor below the threshold.

Real systems still run d=2. The reason is the cache. A single lookup now has to inspect d slots, and those positions are not adjacent to one another. With d=2 the lookup reads two cache lines, while d=4 touches four non-contiguous memory locations. The fact that the threshold analysis was only settled theoretically in 2024 also held adoption back.

Discarding the key and keeping the fingerprint

The cuckoo filter reuses the same kick-out structure but stores only a k-bit fingerprint instead of the original key. That creates one problem. Relocating an evicted element requires its second hash value, and the original key is gone, so it cannot be hashed again.

Partial-key cuckoo hashing solves this with the symmetry of XOR. It ties the two candidate buckets together through the relation below.

b1 = hash(x) mod B
b2 = b1 XOR hash(fingerprint(x)) mod B
 
b2 XOR hash(f) = b1      applying XOR twice returns the original value

The fingerprint f and the current bucket index are enough to compute the alternate bucket. The kick-out chain can therefore continue without ever storing the original key. The price is a constraint: the bucket count has to be a power of two so that the XOR and the modulo do not disagree.

Deletion is a matter of finding the fingerprint and clearing the slot. Two traps hide there. A key inserted twice has to be deleted twice, and deleting the fingerprint of an element that was never inserted can clear the slot of a different key that shares that fingerprint. The second case produces a false negative, which breaks the basic contract of a filter.

Fingerprint collisions cause the same trouble on the false-positive side. If fingerprint(x) equals fingerprint(y), a lookup for y returns true even though y was never inserted. The collision probability is 1/2^k for a fingerprint of k bits, so the target false positive rate is what fixes k.

Where Bloom filters and cuckoo filters diverge

A Bloom filter approximates set membership with an m-bit array and k hash functions. Insertion sets k bits to 1, and a lookup checks whether all k of those bits are 1. Clearing a bit back to 0 would also erase the trace of every other element sharing that bit, which is why deletion is impossible.

In the measurements by Fan et al. (CoNEXT 2014), the space advantage between the two structures splits at the target false positive rate. Driving that rate down forces a Bloom filter to add hash functions, and every lookup then pays for k reads of scattered bits. A cuckoo filter halves its false positive rate for each extra fingerprint bit while still reading only two buckets.

The operational limit comes from the load factor. Kick-out chains grow sharply once the load factor approaches the threshold. Production implementations usually cap it at 80% to 85% and resize past that point.

One bit saved by overlapping the buckets

A 2025 paper (arXiv:2505.05847) changes the bucket boundary itself. The classic structure cuts slots into non-overlapping buckets, which costs a space overhead of 1.365x at a 10-bit fingerprint. The paper introduces overlapping windows instead.

classic bucket  [s0 s1 s2 s3] [s4 s5 s6 s7] [s8 s9 ...]     boundary fixed
window l=2      [s0 s1] [s1 s2] [s2 s3] [s3 s4] ...         overlapped, W = S - l + 1

The first number is the count of hash functions and the second is the number of slots per bucket or window. Overlapping lets several windows share one slot, so the same slot count holds more elements. Storage per key becomes k+2 bits, the k-bit fingerprint plus one selection bit and one window offset bit, down one bit from the earlier k+3. The paper claims this is the smallest space among filters that support online insertion.

A cost comes with it. In the paper's evaluation, lookup speed matches Prefix Filter and VQF, but insertion is slower. The overhead of computing window boundaries lands on the insertion path.

The proof that fingerprints were already optimal

Two theory papers answer how much smaller a fingerprint-based filter can still get.

Kuszmaul and Walzer (STOC 2024) proved that any dynamic filter supporting both insertion and deletion must use n log₂(1/ε) + Ω(n) bits. Here n is the element count and ε is the target false positive rate. The information-theoretic lower bound for a static filter is n log₂(1/ε), so dynamism itself demands a constant number of extra bits per element.

Kuszmaul, Liang, and Zhou (FOCS 2025, arXiv:2510.18129) pinned down that constant. As ε goes to zero, every dynamic filter must use n log₂(1/ε) + n log₂e − o(n) bits, and the fingerprinting technique introduced by Carter et al. in 1978 attains that bound. A technique in use for nearly half a century turns out to be a solution that cannot be improved information-theoretically.

What stands out in the table is that the dynamic lower bound sits below the Bloom filter. That runs against the assumption that supporting deletion has to cost more space. A fingerprint-based design offers deletion and still reaches the bound with less space than a classic Bloom filter. The windowed cuckoo filter from the previous section spends k+2 bits per key, and the dynamic bound is log₂(1/ε) + 1.4427 bits. Mapping fingerprint length onto log₂(1/ε) leaves a gap under 0.6 bits per key.

Capacity remains the open problem. A cuckoo filter has a fixed initial capacity, so data growing beyond the estimate either raises the false positive rate or wastes memory. Aleph Filter (Dayan, Bercea, and Pagh, 2024, arXiv:2404.04703) keeps insertion, lookup, and deletion at O(1). The same paper shows that memory and false positive rate stay stable as data grows without bound. Given an estimate of the final data size, it reaches the same space efficiency as a static filter.

Summary

Cuckoo hashing gives each element two candidate slots and pushes collisions along a kick-out chain, which fixes lookup cost at worst-case O(1). The cuckoo filter layers fingerprints and XOR symmetry on top, continuing the kick-out chain without the original key. Deletion support and a low false positive rate come in return. Deletion produces a false negative when an element that was never inserted is removed, so the caller has to own the insertion history.

The 2025 windowed structure overlapped buckets to save one bit per key. The lower bound proved at FOCS the same year showed that the 1978 fingerprinting technique was already the optimum for dynamic filters. For workloads where the set keeps changing, a fingerprint-based filter is the default, and the remaining choices are the fingerprint length and the load factor cap.