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 in a bucket. Cuckoo hashing limits that cost to a constant. It uses hash functions h1 and h2 with arrays T1 and T2. Key k occupies exactly one of T1[h1(k)] and T2[h2(k)]. A lookup reads two slots, giving O(1) worst-case cost.

Insertion incurs the extra cost. If the target slot is occupied, the new key evicts the existing key and takes its slot. The evicted key moves to its alternate slot and evicts that slot's key if necessary. The name comes from the cuckoo bird, which pushes other eggs from 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, insertion does not terminate. Implementations cap the number of moves and rehash with fresh functions when the cap is exceeded. The two-hash, single-slot configuration has a load threshold near 50%.

Long kick-out chains and rehashes become more likely near that threshold. The 50% figure does not apply directly to a cuckoo filter whose buckets hold several slots.

What extra hash functions buy

With d hash functions (d ≥ 3), each key has d candidate slots and the load threshold rises. For a long time, constant insertion cost below that threshold remained an open question. FOCS 2024 work (arXiv:2401.14394) proved expected O(1) insertion for random-walk d-ary cuckoo hashing at any load factor below the threshold.

More hash functions make each lookup inspect more candidate locations. If locations occupy separate cache lines, the additional memory accesses have a cost. Compare this cost with the space saved at a higher load.

flowchart LR
    K["Key k"] --> H1["Candidate h1(k)"]
    K --> H2["Candidate h2(k)"]
    H1 -->|free slot| DONE["Insert complete"]
    H2 -->|free slot| DONE
    H1 -->|both full| EVICT["Evict one fingerprint"]
    EVICT --> ALT["Compute alternate bucket by XOR"]
    ALT -->|free slot| DONE
    ALT -->|kick limit reached| FAIL["Fail or resize"]

Discarding the key and keeping the fingerprint

A cuckoo filter uses the same kick-out structure but stores only a k-bit fingerprint instead of the original key. Moving an evicted element requires its second hash value. Without the original key, the filter cannot recompute that value by hashing the key.

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 current bucket index are enough to compute the alternate bucket. The kick-out chain can therefore continue without storing the original key. The bucket count must be a power of two to keep XOR and modulo operations compatible.

Deletion finds the fingerprint and clears its slot. A key inserted twice must be deleted twice. Deleting an element that was never inserted can remove a different key with the same fingerprint. This produces a false negative and violates the filter's basic guarantee.

Fingerprint collisions also cause false positives. A lookup examines several slots across two candidate buckets. Its false positive rate therefore exceeds the pairwise fingerprint collision probability $2^{-k}$. With b nearly full slots per bucket, the rate is approximately $2b/2^k$. Choose k using both the bucket size and target false positive rate.

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.

Fan et al.'s CoNEXT 2014 paper reports lower space use than a space-optimized Bloom filter. The comparison covers up to a few billion items and target false positive rates below 3%. The experimental result depends on the paper's bucket size and occupancy. Adding one fingerprint bit approximately halves the false positive rate, while lookup still reads two candidate buckets.

The operational limit depends on the implementation's load threshold. The paper's four-slot buckets operate at about 95% occupancy in its experiments, but changing fingerprint or bucket size changes the failure point. Measure insertion failures and kick counts, then resize before 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 number of hash functions. The second is the number of slots per bucket or window. Overlapping lets windows share slots and store more elements with the same slot count.

Each key uses k+2 bits: a k-bit fingerprint, one selection bit, and one window offset bit. This saves one bit compared with the earlier k+3. The paper claims the lowest space use among filters that support online insertion.

In the paper's evaluation, lookup speed matches Prefix Filter and VQF, but insertion is slower. Calculating window boundaries adds work during insertion.

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 a space lower bound for dynamic filters that support insertion and deletion. These filters need 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/ε). Dynamic operation therefore requires a constant number of extra bits per element.

Kuszmaul, Liang, and Zhou (FOCS 2025, arXiv:2510.18129) established that constant. As ε approaches zero, every dynamic filter needs n log₂(1/ε) + n log₂e − o(n) bits. The fingerprinting technique introduced by Carter et al. in 1978 achieves this bound. This technique, used for nearly half a century, is therefore information-theoretically optimal.

The table's dynamic lower bound is below the Bloom filter's space use. A fingerprint-based design supports deletion and reaches the bound with less space than a classic Bloom filter. This contradicts the assumption that deletion must require more space.

The windowed cuckoo filter uses k+2 bits per key. The dynamic bound is log₂(1/ε) + 1.4427 bits. Mapping fingerprint length to log₂(1/ε) gives a gap below 0.6 bits per key.

Capacity remains a problem. At capacity, a fixed-size cuckoo filter rejects insertions instead of increasing the false positive rate. It must then resize or rebuild. Allocating excessive capacity wastes memory on empty slots.

Aleph Filter (Dayan, Bercea, and Pagh, 2024, arXiv:2404.04703) keeps insertion, lookup, and deletion at O(1). The paper describes control of memory and false positive rate as data grows. With an estimate of final size, the filter reaches static-filter space efficiency.

Summary

Cuckoo hashing uses two candidate locations and a kick-out chain to bound lookup at worst-case O(1). A cuckoo filter uses fingerprints and XOR symmetry to compute an alternate bucket without the original key. Deletion remains safe only when the caller deletes an item that was actually inserted.

The false positive rate depends on fingerprint length and the number of inspected slots. A fixed-size filter also needs resizing before insertions begin to fail. The windowed structure and dynamic-filter lower bound clarify the conditions under which this space cost can shrink further.