The Bloom filter answers "have I seen this?" by smearing every item across several shared bits, one hash function per bit, and can never delete because clearing a bit might belong to someone else too. The Cuckoo filter fixes delete by giving each item its own fingerprint in a specific, findable slot, at the cost of a real insertion-failure ceiling once displacement runs out of room. An XOR filter takes a third path, and gives up something neither of the other two gives up: the ability to add items one at a time. It's built once, from the whole key set at once, by a peeling construction — repeatedly finding an array slot touched by only one remaining key, and pulling that key out of the problem. What's left after peeling is an assignment order that guarantees every key's fingerprint can be reconstructed by XORing exactly three fixed slots together, with no two keys ever fighting over the same slot the way a Cuckoo filter's displacement cascade does.
Every key gets exactly three candidate slots, one from each of three hash functions, each confined to its own third of the array so no two of a key's three slots can ever land on each other. Query XORs the three slots a key hashes to and compares the result to the key's own fingerprint (a short hash, same idea as the Cuckoo filter's fingerprint, here one byte). If they match, the filter reports the item might be present; if they don't, it's definitely absent — same one-sided guarantee as a Bloom filter, just reconstructed by XOR instead of read directly off a bit array.
Build a filter from the same 20 candidate words the Cuckoo Filter demo uses. Unlike that demo, there's
no partial success here — the whole set goes in at once, or the attempt fails outright and a fresh
attempt starts with new hash seeds. Watch how many attempts it actually takes (usually one), how
big the array ends up (≈1.23n, rounded to a multiple of 3), and which three
cells any given word's fingerprint depends on.
m is split into three equal
contiguous thirds, r0, r1, r2. Hash function i
only ever lands inside segment i — this is what guarantees a key's three slots are
always three genuinely different array positions, never two hashes colliding on the same
cell.fingerprint(key) XOR
array[other slot 1] XOR array[other slot 2], using whatever those two other slots already
hold — which is always final by this point, since anything that could still change them was
peeled later and is processed earlier in this reverse walk. That's the whole trick: by the time a
key's own slot is written, its other two slots are locked in for good.function fnv1a(s, seed) {
let h = (0x811c9dc5 ^ seed) >>> 0;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 0x01000193);
}
// finalizer: without this extra mixing the construction still "runs" but fails
// to peel unpredictably as n grows -- see Pitfalls
h ^= h >>> 16;
h = Math.imul(h, 0x85ebca6b);
h ^= h >>> 13;
return h >>> 0;
}
function fingerprint(item) { return (fnv1a(String(item), 0x27d4eb2f) % 255) + 1; }
class XorFilter {
#arraySize; #segSize; #segStart; #seeds; #array;
static build(keys, c = 1.23, maxAttempts = 1000) {
const arraySize = Math.ceil((Math.ceil(c * keys.length) + 32) / 3) * 3;
for (let attempt = 1; attempt <= maxAttempts; attempt++) {
const seeds = [(attempt * 0x2545F491) >>> 0, (attempt * 0x9E3779B1) >>> 0, (attempt * 0x85EBCA77) >>> 0];
const filter = new XorFilter(arraySize, seeds);
if (filter.peelAndAssign(keys)) return { filter, attempts: attempt };
}
return null; // exhausted maxAttempts -- caller should grow c and retry
}
constructor(arraySize, seeds) {
this.#arraySize = arraySize;
this.#segSize = arraySize / 3;
this.#segStart = [0, this.#segSize, this.#segSize * 2];
this.#seeds = seeds;
this.#array = new Uint8Array(arraySize);
}
hslot(i, key) { return this.#segStart[i] + (fnv1a(String(key), this.#seeds[i]) % this.#segSize); }
peelAndAssign(keys) {
const slots = Array.from({ length: this.#arraySize }, () => new Set());
keys.forEach((k, idx) => { for (let i = 0; i < 3; i++) slots[this.hslot(i, k)].add(idx); });
const queue = [];
for (let s = 0; s < this.#arraySize; s++) if (slots[s].size === 1) queue.push(s);
const peeled = new Array(keys.length).fill(false);
const order = [];
while (queue.length) {
const s = queue.pop();
if (slots[s].size !== 1) continue; // stale queue entry, already resolved elsewhere
const idx = [...slots[s]][0];
if (peeled[idx]) continue;
peeled[idx] = true;
order.push({ idx, slot: s });
for (let i = 0; i < 3; i++) {
const sl = this.hslot(i, keys[idx]);
slots[sl].delete(idx);
if (slots[sl].size === 1) queue.push(sl);
}
}
if (order.length !== keys.length) return false; // a real stuck 2-core, not just bad luck
for (let j = order.length - 1; j >= 0; j--) {
const { idx, slot } = order[j];
const key = keys[idx];
let x = fingerprint(key);
for (let i = 0; i < 3; i++) { const sl = this.hslot(i, key); if (sl !== slot) x ^= this.#array[sl]; }
this.#array[slot] = x;
}
return true;
}
mightContain(key) {
let x = 0;
for (let i = 0; i < 3; i++) x ^= this.#array[this.hslot(i, key)];
return x === fingerprint(key);
}
}Verified three ways. (1) Every one of the 20 demo words comes back mightContain() ===
true after construction — 0 false negatives, checked directly, not assumed. (2) A
200,000-query false-positive sweep against strings guaranteed absent from the 20-word set: 606
false positives (0.303%), close to the 8-bit fingerprint's theoretical ceiling of 1/256
(≈0.391%) — measured below theory here, which is expected (the theoretical figure is an
upper bound on the collision rate, not an exact prediction). (3) Construction success itself: a
first version's fnv1a without the finalizer mixing steps shown above (just the raw
FNV multiply-and-xor loop, then return) looked completely fine at small n — the
20-word demo above still built first-try — but running 300 trials at n = 1,000
(fresh random keys each trial, one construction attempt per trial, no retries) that weak version
only completed peeling 47.0% of the time. Switching only the hash finalizer, nothing else, to the
version shown above raised that to 90.0% over the same 300 trials. See Pitfalls for why bit
diffusion, not hash-seed independence, turned out to be the actual variable. See
/tmp/xorfilter/*.js, scratch, not committed.
The hash functions need real bit diffusion — being separately seeded isn't
enough on its own. The instinct when something goes wrong with three hash functions is to
suspect they're not independent enough — maybe deriving one from the other two, or reusing seeds
carelessly. That was tested directly and ruled out: setting the third seed to seed0 XOR
seed1 (deliberately correlated) made no measurable difference against three genuinely
independent seeds, both landing around 91-97% success across n from 100 to 1,000 (100
trials each). What actually mattered was whether each individual hash function scrambles its input
well enough on its own. Dropping just the finalizer mixing steps (h ^= h >>> 16; h =
Math.imul(h, 0x85ebca6b); h ^= h >>> 13;) from fnv1a — keeping three
still-independently-seeded copies of the weakened function — dropped peel success from 90.0% to
47.0% at n = 1,000 over 300 trials each, and the weak version's success rate doesn't
even fall off smoothly as n grows: separate spot checks at n = 100, 300,
500, 2,000 came back 6%, 28%, 1%, and 47% respectively with the weak hash — no trend, just
unreliable, because a hash with poor avalanche sends clusters of different keys to the same slot
combinations, and clusters are exactly what turn peeling into a stuck 2-core. Three independently
seeded copies of a well-mixed hash removed that unpredictability entirely.
Construction can fail outright, and that's normal, not a bug to
avoid. A stuck 2-core isn't a bug in the code above — it's a real, expected possibility of
random 3-uniform hypergraph peeling, which is why build() loops on
maxAttempts. With a properly-mixed hash and the standard slack factor c =
1.23, that loop rarely needs more than one pass in practice: measured average attempts to
succeed were 1.06 at n = 1,000, 1.13 at n = 10,000, and 1.00 at n =
100,000 (100 trials each, worst case seen was 2 attempts). A caller that assumes the first
attempt always works and skips the retry loop entirely will intermittently fail to build a filter
for no visible reason — same class of silent-until-it-isn't hazard as the Cuckoo filter's
unchecked insertion failure, just at construction time instead of per-item.
This is a static structure — there's no add after build, and
no delete at all. Every array slot's value depends on every other key that
was peeled after it in construction order, chained back through the XOR reconstruction. Setting one
more key's fingerprint into the array without redoing the whole peel would silently corrupt
whichever earlier keys happen to share a slot with it — there's no local, safe way to splice a
single new key in the way a Cuckoo filter can insert one at a time. A workload that needs
incremental updates needs the Cuckoo filter (or a Bloom filter, if delete is never needed either);
an XOR filter fits a key set that's known up front and rebuilt wholesale when it changes, not one
that grows continuously.
k-hash loop or the Cuckoo filter's two-bucket check, paid for entirely at
construction time instead of at query time.-log₂(p)/ln 2 bits per item) needs about 11.54 bits per item
for that same false-positive target — a real, if modest, space advantage from spending the
savings at build time rather than query time.Time: mightContain is O(1) worst case, always
exactly three fixed reads plus two XORs, regardless of load or how the filter was built. Build is
O(n) expected — one peeling pass touches each key and each of its three slots a
bounded number of times — but has no guaranteed single-attempt bound; a stuck 2-core forces a
full-array retry with fresh seeds, measured at 1.00-1.13 average attempts above. There is no
add or delete after construction at any complexity. Space:
O(n), roughly 1.23n one-byte slots for an 8-bit fingerprint (≈9.84
bits/key at scale, measured above) — smaller per key than the Bloom filter's own optimal formula at
the same false-positive target, and with no per-slot bucket structure to maintain the way the
Cuckoo filter's buckets need.
This site's guide, Choosing a Probabilistic Structure, compares this entry against Bloom Filter and Cuckoo Filter side by side.