Xor Filter

A static membership filter: you hand it the entire key set once and it builds an immutable fingerprint array, no incremental insert. In exchange for that immutability it beats Bloom and Cuckoo filters on both space (~9.84 bits/key at ~0.39% false positives) and query speed (a fixed 3 lookups + one XOR, no probing or eviction).

How it works

Every key is reduced to a 32-bit hash, which deterministically picks three candidate slots (one from each of three equal-sized blocks h0/h1/h2) and an 8-bit fingerprint. The array is sized to about 1.23× the number of keys, split evenly across the three blocks.

Construction works by peeling: repeatedly find a slot that only one remaining key still touches (its "degree" is 1), record that key against that slot, then remove it from its other two slots and repeat, cascading like cuckoo hashing but only during construction. If every key gets peeled, fingerprints are assigned in reverse peel order, so each key's designated slot is set to exactly the value that makes its three slots XOR back to its fingerprint. If peeling stalls before every key is removed (rare, with ~1.23× overprovisioning), the whole attempt is discarded and retried with a fresh hash seed.

contains() just recomputes the same three slots and fingerprint, XORs the three stored values together, and compares against the fingerprint: three reads and two XORs, always, with no cascading or probing needed.

Interactive demo

Keys built8
Array length42
Bits / entry42.00
Build attempts1
h0
0
0
0
0
0
0
69
0
0
0
0
0
0
0
h1
0
0
0
0
0
0
0
a2
79
0
0
0
41
0
h2
0
0
0
51
0
0
0
fe
0
0
0
20
0
67
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
XorFilter.build(items[]): { filter, success, attempts, events }One-shot construction over the full key set (de-duplicated). Retries with a new hash seed if peeling stalls.O(n) expected, O(n × attempts) worst case
contains(item): booleanRecompute 3 slots + fingerprint, XOR the stored values, compare. No false negatives.O(1): 3 reads + 2 XORs
bitsPerEntry: numberBits stored per key, including the ~1.23× overprovisioned array.—

References

Original papers

Library implementations

Real-world use cases