↩ back to Probabilistic

Cuckoo Filter

The Bloom filter page's whole design rests on one rule that turns out to matter more than it first looks: bits only ever get set, never cleared, because clearing one might silently break some other item that also needs it. That rule is exactly why a standard Bloom filter can't support delete. A Cuckoo filter keeps the same trade — fixed memory, no stored keys, a tunable false-positive rate — but changes what gets stored. Instead of smearing each item across several shared bits, it stores a small fingerprint (a few bits of hash, not the item itself) in one specific slot, using the same displacement idea as cuckoo hashing. A specific slot can be found again and cleared on its own, without touching anyone else's — so delete becomes a real, first-class operation, not something that needs a whole separate counting variant.

Every item gets exactly two candidate buckets, each holding a small fixed number of slots (b, here 2). i1 comes from hashing the item directly. The fingerprint fp is a short hash of the item, stored in whichever slot it lands in. i2 comes from i1 XORed with a hash of just the fingerprint — not the original item — which is the trick that makes displacement possible: applying that same XOR to i2 and fp lands back on i1, so a fingerprint can be kicked out of either of its two buckets and still know its other home, having forgotten the original item entirely. Insert tries i1, then i2; if both are full, it picks one, evicts whichever fingerprint is sitting there, places the new one, and goes to relocate the evicted fingerprint at its other bucket — the same cascading displacement cuckoo hashing uses, just moving fingerprints instead of whole key/value pairs.

Try it

Add an item and watch its fingerprint land in one of its two buckets — or, once both are full, watch a real displacement cascade play out. Query checks both buckets for a matching fingerprint; delete clears the first match it finds. The table below is deliberately tiny (8 buckets, 2 slots each — 16 total) so it fills up fast and failures are easy to see.

Load the sample: 20 candidate words go in, in order. The first several place directly with no kicks. frog needs 1 kick, rat needs 5, cow needs 4 — real displacement cascades, not staged ones. bee, ant, pig, hen, and elk all fail outright: not because the table is completely full (one slot is still empty when bee fails), but because neither of their two buckets has room and every displacement path out of them runs out of kicks before finding one — see Pitfalls for what that means for insertion generally. 15 of 20 succeed, filling 15 of 16 slots.

Then query mole (really added, reports present) and stoat (never added — but its fingerprint and both its candidate buckets are identical to mole's, verified directly against the real hash functions below, so it reports a genuine false positive). Then delete stoat: the filter has no way to know it was never really added, so it clears the matching fingerprint slot anyway — which is mole's real entry. Query mole again afterward and it now reports absent, even though it was never deleted. See Pitfalls for why this isn't specific to this demo's word list.

Core operations

• fingerprint(item) — a short hash of the item (here one byte, 1-255; 0 is reserved to mean "empty slot"). Never the item itself.
• i1(item) — hash(item) & mask, the item's first candidate bucket.
• i2(i, fp) — i XOR (hash(fp) & mask), computable from either of a fingerprint's two buckets plus the fingerprint alone — this symmetry is what lets a fingerprint be relocated without ever knowing the original item.
• add(item) — place the fingerprint in i1 or i2 if either has a free slot; otherwise displace an existing fingerprint and cascade. O(1) expected, bounded worst case by a fixed kick limit.
• mightContain(item) — check both candidate buckets for a matching fingerprint. Exactly 2 buckets, O(1) worst case, same guarantee as cuckoo hashing's two-probe get.
• delete(item) — clear the first matching fingerprint found in either bucket. O(1), no counters, no separate variant needed — but only sound if the item was really added (see Pitfalls).

Reference implementation

function fnv1a(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

function djb2(s) {
  let h = 5381;
  for (let i = 0; i < s.length; i++) {
    h = (Math.imul(h, 33) + s.charCodeAt(i)) >>> 0;
  }
  return h >>> 0;
}

class CuckooFilter {
  #numBuckets; #mask; #b; #maxKicks; #buckets;

  constructor(numBuckets, slotsPerBucket, maxKicks) {
    this.#numBuckets = numBuckets; // must be a power of 2 — see Pitfalls
    this.#mask = numBuckets - 1;
    this.#b = slotsPerBucket;
    this.#maxKicks = maxKicks;
    this.#buckets = Array.from({ length: numBuckets }, () => new Array(slotsPerBucket).fill(0));
  }

  #fingerprint(item) { return (djb2(String(item)) % 255) + 1; } // 1-255, 0 = empty
  #i1(item) { return fnv1a(String(item)) & this.#mask; }
  #i2(i, fp) { return (i ^ (fnv1a(String(fp)) & this.#mask)) & this.#mask; }
  #emptySlot(i) { return this.#buckets[i].findIndex(s => s === 0); }

  add(item) {
    const fp = this.#fingerprint(item);
    const i1 = this.#i1(item);
    const i2 = this.#i2(i1, fp);
    let slot = this.#emptySlot(i1);
    if (slot !== -1) { this.#buckets[i1][slot] = fp; return true; }
    slot = this.#emptySlot(i2);
    if (slot !== -1) { this.#buckets[i2][slot] = fp; return true; }

    // both starting buckets are full: displace, tracking every swap so a failed
    // attempt (table too full along this path) can be rolled back cleanly
    let i = i1, f = fp;
    const swaps = [];
    for (let k = 0; k < this.#maxKicks; k++) {
      const s = 0; // fixed slot choice, not randomized — see Pitfalls
      const evicted = this.#buckets[i][s];
      swaps.push({ bucket: i, slot: s, was: evicted });
      this.#buckets[i][s] = f;
      f = evicted;
      i = this.#i2(i, f);
      const target = this.#emptySlot(i);
      if (target !== -1) { this.#buckets[i][target] = f; return true; }
    }
    for (let j = swaps.length - 1; j >= 0; j--) {
      this.#buckets[swaps[j].bucket][swaps[j].slot] = swaps[j].was;
    }
    return false; // rolled back — filter unchanged, item not added
  }

  mightContain(item) {
    const fp = this.#fingerprint(item);
    const i1 = this.#i1(item);
    const i2 = this.#i2(i1, fp);
    return this.#buckets[i1].includes(fp) || this.#buckets[i2].includes(fp);
  }

  delete(item) {
    const fp = this.#fingerprint(item);
    const i1 = this.#i1(item);
    const i2 = this.#i2(i1, fp);
    let slot = this.#buckets[i1].indexOf(fp);
    if (slot !== -1) { this.#buckets[i1][slot] = 0; return true; }
    slot = this.#buckets[i2].indexOf(fp);
    if (slot !== -1) { this.#buckets[i2][slot] = 0; return true; }
    return false;
  }
}

Verified three ways. (1) A first version without the rollback (return false immediately on hitting the kick limit, leaving whatever had already been displaced in place) was tried first and caught its own bug: across 3,000 sequential inserts into a 256-slot filter, 256 succeeded as expected but 253 of those 256 successfully inserted items came back mightContain() === false later — a failed insert near capacity was silently discarding an earlier real entry it had displaced along the way before giving up. Adding the swap-tracking rollback shown above fixed it: rerunning the same 3,000-insert sequence, plus a 500-trial randomized sweep varying bucket count, b, and fill level (22,040 total post-insert membership checks), zero false negatives among successfully-added items in both. (2) The i1/ i2 symmetry property itself — that computing i2 from i1 and back again returns i1 — checked directly across 1,000 items. (3) The demo's own 20-word walkthrough (which words succeed, how many kicks each takes, which five fail) and the mole/stoat collision reproduced exactly against this exact code, not hand-computed. See /tmp/cuckoofilter/*.js, scratch, not committed.

Pitfalls

Insertion can fail — a real, visible ceiling the Bloom filter doesn't have. A Bloom filter's add always succeeds; get enough items in and the false-positive rate just climbs. A Cuckoo filter's add can return failure outright once displacement runs out of kicks, as the demo's own bee/ant/pig/hen/ elk failures show — and, as those same failures show, this can happen well before the table is literally full: bee fails with a free slot still sitting elsewhere in the table, because that free slot isn't reachable from bee's own two buckets within the kick budget. A production filter has to actually check add's return value and resize or reject — there's no silent degradation to fall back on.

How full it can get before that happens depends on bucket size b, and is empirical, not a clean formula. A separate large-scale check (2,048 buckets, b of 1, 2, and 4, kick limit 500, inserting freshly-random distinct keys until 200 consecutive failures) reached roughly 99%, 99.8%, and 99.8% fill respectively before giving up — all far past where the tiny 16-slot demo above starts failing at 93.75% (15/16), because the demo's small table gives displacement chains far less room to maneuver before running into another chain. The general shape holds either way: bigger buckets (larger b) mean more choices at insert time and push the failure point higher, at the cost of more wasted space per bucket when it's nearly empty.

Delete is only sound if the item was really added — sharper than the Bloom filter's counting-variant hazard, and needs no counters to trigger. delete just clears whatever fingerprint matches in either candidate bucket; it has no way to tell a genuine member from a false positive that merely reports one. The live demo's mole/stoat pair is a real collision, not staged: both hash to fingerprint 38 and both land on bucket set {2, 4} under this exact reference implementation. Deleting stoat — never actually added — clears the fingerprint-38 slot the same as deleting a true member would, and that slot is mole's. mole then reads absent, having never been touched directly. Same underlying hazard as the Bloom filter's counting-mode delete, but here it's the structure's default behavior, not an opt-in mode — the only real defense is the same one: never call delete on an item without tracking its true membership somewhere else first.

numBuckets must be a power of two. The i2 = i1 XOR (hash(fp) & mask) trick only stays reversible — i2 XORed the same way lands back on exactly i1 — when mask is a contiguous run of low bits, which only numBuckets - 1 gives for a power-of-two numBuckets. Picking a non-power-of-two bucket count (say, 10) and reducing with % instead breaks that symmetry: a fingerprint displaced out of i2 computes a "return" index that isn't reliably i1 anymore, and lookups checking only the textbook two buckets can miss entries that displacement silently pushed somewhere else — confirmed by rerunning the symmetry check above with numBuckets = 10 and a plain % reduction: the "i2-then-back-to-i1" round trip fails on 489 of 1,000 items (48.9%).

Where Cuckoo filters show up

• Anywhere a Bloom filter would be used but items also need to be removed — caching layers that evict entries, deduplication windows over a sliding time range, or any membership set that isn't purely append-only.
• Network packet processing and flow tracking. The same bounded worst-case lookup cost that makes cuckoo hashing a fit for hardware lookup tables applies here too, with the added ability to age out flows that have ended.
• Storage engines wanting a smaller footprint at very low target false-positive rates. At the low end of typical false-positive targets, cuckoo filters can need less space per item than a Bloom filter for the same rate, because a fingerprint-and-bucket scheme doesn't share bits across unrelated items the way a plain bit array does.

Complexity

Time: mightContain and delete are O(1) worst case — exactly two buckets checked, always, regardless of load, the same guarantee cuckoo hashing gives get. add is O(1) expected but has no small fixed worst-case bound: a displacement cascade can run all the way to the kick limit, and unlike cuckoo hashing there's no automatic resize built in above — a caller has to detect failure and grow the table itself. Space: O(n), but each stored item costs only a fingerprint (a handful of bits) rather than a full key, and unlike the Bloom filter's shared-bit array, an item can actually be found and cleared again without disturbing anyone else's fingerprint — the trade this whole structure exists to make.

This site's guide, Choosing a Probabilistic Structure, compares this entry against Bloom Filter and the site's other fixed-memory unbounded-stream structures side by side.