DEV Community: Federico Kereki

Part 14: Answers to Questions

Federico Kereki — Fri, 30 Oct 2026 11:58:30 +0000

In which we finish the chapter by providing answers to all the questions in the text.

Chapter 11½

Here are all the answers to the questions in this new chapter.

11½–1. Do it with class!

To implement an SBF using classes, we may use private (#) attributes, so only add and find will be visible. Assume we are importing the hashWithSeed function from another module. From our code (see below) we would only export StandardBloomFilter.

const EPSILON = 0.01;
const LN2 = Math.log(2);
const LN2_SQ = LN2 * LN2;

class StandardBloomFilter {
  #b;
  #h;
  #bits;

  constructor(n, eps = EPSILON) {
    this.#b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
    this.#h = Math.max(1, Math.round((this.#b / n) * LN2));
    this.#bits = new Array(this.#b).fill(false);
  }

  #getIndices(value) {
    return Array.from(
      { length: this.#h },
      (_, i) => hashWithSeed(String(value), i) % this.#b
    );
  }

  add(value) {
    for (const idx of this.#getIndices(value)) {
      this.#bits[idx] = true;
    }
  }

  find(value) {
    return this.#getIndices(value).every((idx) => this.#bits[idx] === true);
  }
}

We can also hide internal details by using closures. When you create a new SBF by calling newClosureBloomFilter, you get an object with just the add and find methods; you cannot access b, h, or the bits array, for example.

const EPSILON = 0.01;
const LN2 = Math.log(2);
const LN2_SQ = LN2 * LN2;

const newClosureBloomFilter = (n, eps = EPSILON) => {
  const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
  const h = Math.max(1, Math.round((b / n) * LN2));
  const bits = new Array(b).fill(false);

  const getIndices = (value) =>
    Array.from({ length: h }, (_, i) => hashWithSeed(String(value), i) % b);

  const add = (value) => {
    for (const idx of getIndices(value)) {
      bits[idx] = true;
    }
  };

  const find = (value) =>
    getIndices(value).every((idx) => bits[idx] === true);

  return { add, find };
};

11½–2. Getting down to bits

After calculating how many bits (b) we require, we can use an Uint8Array whose size is b/8 rounded up, since each entry in the array provides 8 bits. To access a given bit, first calculate which array entry it is in, then which bit to test. The modified functions are below.

const newStandardBloomFilter = (n, eps = EPSILON) => {
  const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
  const h = Math.max(1, Math.round((b / n) * LN2));

  return {
    b,
    h,
➊  bits: new Uint8Array(Math.ceil(b / 8))
  };
};

const add = (filter, value) => {
  for (const idx of getIndices(filter, value)) {
➋  const byteIndex = idx >> 3;
➌  const bitMask = 1 << (idx & 7);
➍  filter.bits[byteIndex] |= bitMask;
  }
};

const find = (filter, value) =>
  getIndices(filter, value).every((idx) => {
    const byteIndex = idx >> 3;
    const bitMask = 1 << (idx & 7);
➎  return (filter.bits[byteIndex] & bitMask) !== 0;
  });

The first change is that instead of creating a common array, we produce an Uint8Array; using Math.ceil deals with the case in which b is not divisible by 8, making the array just a tad bigger than needed. (The waste is minimal; just a few bits!) We can find which byte to modify by dividing idx by 8 ➋ which is achieved by using the >> binary right shift operator. Which bit to set is the remainder of idx divided by 8; this is also achieved by using a bitmask (AND-ing a number with 7 produces just the lower-order three bits.) Finally ➍ we use the binary | OR operator to set the needed bit. When doing a search ➎ everything works the same way, but we use the binary AND operator to test the required bit.

11½–3. A powerful solution

We wanted to ensure that the bitmap size and the 2nd hash function have no common divisors. If the bitmap size is a power of 2, its only factors are powers of 2. On the other hand, if the hash function is odd, it cannot be divided by 2. Thus, we are guaranteed that no loops can happen. The changed code is shown below; we just modify the sizing part.

➊ const nextPowerOfTwo = (n) => 2 ** Math.ceil(Math.log2(n));

const newDoubleHashingBloomFilterPowerOfTwo = (n, eps = EPSILON) => {
➋const b = nextPowerOfTwo(Math.ceil(-(n * Math.log(eps)) / LN2_SQ));
  const h = Math.max(1, Math.round((b / n) * LN2));

  return {
    b,
    h,
    bits: new Array(b).fill(false)
  };
};

The nextPowerOfTwo function ➊ finds the next highest power of two for a number. Pick a number; say 10. If you take the logarithm in base 2, you get 3.3219… so 2³ is less than 10, and 2⁴ is greater; the latter is the result we need. We use the function ➋ to determine the bitmap size. The only disadvantage of this fix is that you may end up needing almost twice the size you'd really need. For instance, if you calculated that you needed a bitmap with 1,025 bits (just 1 beyond 2¹⁰ bits) you'd require a 2,048-sized one instead (2¹¹ bits).

11½–4. Over the top?

A "stuck" counter will never go down to zero, so any value relying on that count to determine "present" will always show as present. In effect, the filter loses the ability to report items "absent" through that count again, even if all the items that caused the saturation are eventually deleted. This is a graceful degradation toward more false positives, which is what we tolerate, rather than toward false negatives, which we never allow.

11½–5. Why not make it simpler?

With the suggested change, all slots would share the same object with rem, isOcc, isCont, and isShifted attributes, instead of having separate, independent ones.

11½–6. Unneeded test?

After calling locateRun we know we are at the start of a run. We want to check later whether we reach the start of another run (and then fail the search) but we cannot fail this run. Excluding the test would cause the loop to immediately stop.

11½–7. Add it again, Sam

The current logic will not detect the repetition and will add the repeated remainder after the current ones equal it. In the loop ➏ we should specifically check for equality, and in that case simply return.

11½–8. It all comes out in the wash

For a given set of additions and removals (assuming you do not try to remove a value before it was added) the result is always the same. To figure this out, consider that if you have separate clusters, whatever you do in one doesn't affect the sequence of values in the other. Also, within a cluster, runs are in strict quotient order, and each run is in remainder order.

11½–9. If at first you fail…

This could also fail; you cannot guarantee that the second hash calculation won't also return 0. The probability is 1 in 2^(2_p_), but it's not zero.

11½–10. Let it Be

The CF would still work, but one value (the one in the final loop pass) that was previously there could be gone, and a new one may now be in the filter. There is a small possibility (1 in 2bs) that the last kicked value happened to be just the one we were trying to add, but the most likely result would be that some other value would end kicked out.

11½–11. Some like it short

The following code does the job; instead of destructuring indices into i1 and i2 and checking each bucket by hand, we keep the array and let .some test each index. It returns true as soon as one bucket contains the fingerprint, which is the same short-circuit behavior as the original ||. The code looks shorter, but it's still two lines!

const find = (filter, item) => {
  const { fingerprint, indices } = twoBuckets(filter, item);
  return indices.some(i => filter.buckets[i].includes(fingerprint));
};

Want to get the book?

If you want the original, complete book, you can find it at the publisher, No Starch Press, or at Amazon, Barnes & Noble, Books-A-Million, Bookshop, Powell's Books, Target, or Walmart, in either paperback or e-book format.

Part 13: Other Filters

Federico Kereki — Fri, 30 Oct 2026 11:50:21 +0000

In which we comment on several other options for implementing filters, derived from the ones we've already seen.

Other Options

The filters we've seen aren't the only ones, and many enhancements exist; in this section, we'll cover a few and note how they differ from the ones we've already discussed. Links to the original articles will be included, so you can learn more.

However, we aren't trying to cover every variant and development; that would require a far longer article and would probably be out of date as soon as it's published, so googling for more possibilities is up to you!

Let's go with just half a dozen important options.

Counting Quotient Filters extend QFs in two ways: they restructure metadata bits to obtain fast lookups at high load factors (even around 95%) and store counts in the table so repeated elements are included only once, saving space. Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro created this structure and described it in their paper, "A General-Purpose Counting Filter: Making Every Bit Count".
Vector Quotient Filters also target performance at high load factors, with small extra space cost. They are built from small blocks that behave like miniature QFs; another difference is that when an item may go into two free blocks, they pick the less full one to better balance the load. This structure was described in the "Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design" article by Prashant Pandey, Alex Conway, Joe Durie, Michael A. Bender, Martin Farach-Colton, and Rob Johnson.
Morton Filters are a redesign of CFs, by Alex Breslow and Nuwan Jayasena, who described it in their "Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity" paper. The filter combines biasing (most items are placed with a single hash), compression (fullness counters track the load of each logical bucket), and overflow tracking (an array records overflowed blocks, so find knows whether to check a second location). The paper reports lookups up to 2.5✕ faster, insertions up to 15.5✕ faster, and deletions up to 1.6✕ faster than the cuckoo filter, while keeping space comparable. The gains are largest at high load, where cuckoo insertions slow down because of long eviction chains.
Vacuum Filters, by Minmei Wang, Mingxun Zhou, Shouqian Shi, and Chen Qian (see their "Vacuum Filters: More Space-Efficient and Faster
Replacement for Bloom and Cuckoo Filters" paper) do not need a table whose length is a power of 2 (avoiding unnecessary storage) by dividing it into chunks of L consecutive buckets (L being a power of 2) and keeping both candidates for an item in the same chunk, which improves cache locality. On average, they use 25% less space than CFs, which is their main advantage.
Binary Fuse Filters are a direct successor to XFs, and in fact they were created by the same authors, Thomas Mueller Graf and Daniel Lemire, who described the structure in 2022 in their "Binary Fuse Filters: Fast and Smaller than XOR Filters" article. They keep the XF's query mechanism and nearly the same simple code. The idea is that the table is cut into many small segments laid in a row, and each value uses three consecutive segments instead of three positions each at one third of the array, and this structure requires only about 13% extra space instead of 23% for an XF.
Ribbon filters are also a descendant of the XF, and were created by Peter Dillinger and Stefan Walzer, who introduced the concept in their "Ribbon filter: practically smaller than Bloom and Xor" paper. Instead of having each value depend on several randomly distributed columns, each depends on a few consecutive columns with a varying starting column. This produces a system of equations that looks like a wavy diagonal band, which can be solved by an algorithm similar to Gaussian elimination. Space overhead is usually below 10% and can even go under 1% with some extra engineering.

Bye! In this series of articles, we've discussed Probabilistic Searching and studied several filters. This complements chapters 9 ("Searching") and 11 ("Bags, Sets, and Maps") in my book, with alternative requirements and implementations.

Want to get the book?

Part 12: XOR Filters

Federico Kereki — Thu, 29 Oct 2026 10:45:43 +0000

In the previous articles in the series, we saw several implementations of filters with a common set of operations, including additions and (not always) removals. Here we'll study XOR Filters, which after creation do not permit any change to its values, but provide great performance with low memory requirements.

XOR Filters

An XOR Filter (XF) is another probabilistic search data structure, invented rather recently by Thomas Mueller Graf and Daniel Lemire in their 2020 article "XOR Filters: Faster and Smaller Than Bloom and Cuckoo Filters". Like the previous filters we saw, if asked whether some value is stored in it, it will reply either "absent" with 100% certitude (no false negatives), or "may be present" (with a certain probability of a false positive). Compared to the previous filters, an XF is smaller and faster to query, but at a cost: you build it once from the full data set, and you cannot add or remove values afterward unless you rebuild it from scratch.

(Another difference we had already mentioned in a previous article is that the create operation will take the whole array of items to be stored instead of just the expected number, and there will be no add or remove operations, just find to search the filter.)

How does an XF work? The core idea is to use an array (call it B) divided into three blocks of p-bit slots; the original article allowed different block sizes, but for simplicity we'll make them equal length. For each x value, we have:

three hash positions (h₀(x), h₁(x), and h₂(x)), one for each block
a p-bit fingerprint fp(x)

The array is built in a special way (which we'll soon see) so for every key in the set, it holds that fp(x) = B[h₀(x)] XOR B[h₁(x)] XOR B[h₂(x)]_. So, how do we query it? To check whether a value is in the XF, compute its fingerprint and hashes, then check whether the equality holds; if not, the value definitely isn't in the XF.

Sizing an XOR Filter

Let's start with the fingerprint size. If x was never inserted in the XF, the three cells hold values determined by other keys, and the XOR will in effect produce a random p-bit number, which will match fp(x) with false-positive probability ε=2^(‑p), so p=8 gives ε≈ 0.39%, p=16 gives ε ≈ 0.0015%, and p=24 goes down to 0.00000596%.

Now, for the array size. For n values, the array size is about 1.23_n_; for smaller n, adding 32 is recommended. The 1.23 constant comes from a threshold for a "peeling" graph algorithm we'll use; that number makes it very probable that the procedure succeeds.

The following code is part of the XF creation function; we'll get to the rest later.

const EPSILON = 0.01;

const createXorFilter = (items, eps = EPSILON) => {
➊const p = Math.ceil(Math.log2(1 / eps));
  if (p > 24) {
    throw new Error(
      "XOR filter: epsilon exceeds 24-bit fingerprint limit"
    );
  }

➋const s = Math.ceil((1.23 * items.length) / 3);

  if (items.length === 0) {
    return { p, seed: 0, s: 0, b: [] };
  }

  // array generation code, clipped out

};

According to the formula for ε ➊ we can calculate the number of bits by taking logarithms; we use the ceiling function for safety; longer fingerprints reduce the false positive probability. For simplicity, we want the length of the array to be a multiple of 3 ➋ so we calculate the block size using the ceiling function.

The returned object has:

p is the fingerprint length
seed is used for the three hashing functions
s is the length of each block
b is the generated array; its length is 3*s

We'll see the rest of the code soon (which includes how to calculate the contents of the b array) but let's look at the fingerprint and hashes now.

➊const fingerprintOf = (value, bits) =>
  hashWithSeed(value, 0) & ((1 << bits) - 1);

➋const h0 = (value, seed, s) =>
  hashWithSeed(value, 3 * seed + 1) % s;

const h1 = (value, seed, s) =>
  s + (hashWithSeed(value, 3 * seed + 2) % s);

const h2 = (value, seed, s) =>
  2 * s + (hashWithSeed(value, 3 * seed + 3) % s);

➌const indicesOf = (value, seed, s) => [
  h0(value, seed, s),
  h1(value, seed, s),
  h2(value, seed, s)
];

To find the fingerprint ➊ we use the same hashWithSeed function we've been using, masking it to keep just a given number of bits; when using the function, we'll pass the p value we calculated. Next ➋ we have the three hash functions; we pass the block size s and we use three different seeds, so the hashes are independent. Finally ➌ the indicesOf function just returns an array with the three calculated hashes; we'll use it for searching.

We're still missing the rest of the XF creation code, but we can look at how to search it with some examples. See Figure 11½–24.

Figure 11½–24: Searching an XOR Filter for the 6 added values

We created the XF with the 6 values on the left: GROUCHO, HARPO, CHICO, ZEPPO, GUMMO, and BROTHERS. At the top of the image, we have the array with 9 values, divided into three blocks. The values for the slots were calculated by the algorithm we'll introduce in the next section. For each value, we have its hexadecimal 8-bit fingerprint (fp) and the three calculated hashes.

How do we search? Take GROUCHO, for example:

Calculate its fingerprint (3A)
Calculate its three hashes, one into each block
Calculate the XOR of the three corresponding slot values, 7C, C5, and 83; the result is 3A
Since the fingerprint and the XOR result match, the search is successful

Let's look at two searches for values not in the original set: ABBOTT, which is reported as not being in the set, and COSTELLO, which produces a false positive. See Figure 11½–25.

Figure 11½–25: A failed search and a false positive

What happens in these cases?

For ABBOTT, its fingerprint is 42, its slot values are 89, A6, and 83 and the XOR of these three values is AC, which doesn't match 42 - we get a 100% negative
For COSTELLO, the fingerprint is 46, which happens to match the XOR of the three slots, so we get a false positive.

The search code is as follows.

const find = (filter, value) => {
➊if (filter.s === 0) return false;
➋const [i1, i2, i3] = indicesOf(value, filter.seed, filter.s);
➌return (
    fingerprintOf(value, filter.p) ===
    (filter.b[i1] ^ filter.b[i2] ^ filter.b[i3])
  );
};

First, we check ➊ whether the XF is empty; it doesn't make sense to return a false positive when we know it's empty. Then, we find the three positions to check ➋ and finally we compare the calculated fingerprint with the XOR of the three positions ➌.

Now let's finish by completing the XF creation code.

Creating an XOR Filter

The key detail is how to calculate the B values so the XOR results match the expected fingerprints. Let's start by looking at which slots are involved for each value; see Figure 11½–26.

Figure 11½–26: The "peeling" algorithm decides which slot belongs to which entry

We have to assign values to the slots so the XOR works. Let's see:

BROTHERS is the only value that needs slot #5; given the values for slots #2 and #8, we can calculate the value for slot #5 so the XOR produces the correct fingerprint. We can "peel" BROTHERS off, and after determining the rest of the slots, we can come back to it and finish the job by calculating slot #5. We will say that BROTHERS owns slot #5 and uses slots #2 and #8. Also, let's forget the BROTHERS row of the table for now; imagine it gone.
GROUCHO is a similar case; it's the only value that needs slot #7, so it will own it (and use slots #0 and #3); we'll "peel" it off for later (when we'll be able to set slot #7 so the XOR calculation works out) and ignore that row for now.
ZEPPO is interesting; it needs slots #2, #4, and #6, but having "forgotten" the rows for BROTHERS and GROUCHO, we can peel ZEPPO off and let it own slot #2. When the time comes, we'll be able to calculate slot #2 so the XOR produces the correct fingerprint.
To sum up the rest, CHICO can be peeled off next, owning slot #0; then HARPO owning slot #3; and finally GUMMO owning slot #4.

What comes next? Initially, all slots are set to 00. Let's walk backward through the set of peeled values.

We can let slots #1 and #8 be 00 and set slot #4 to 17 to match the fingerprint to GUMMO. Three slots are now final.
For HARPO we already have slot #1 set to 00; we can let slot #6 at 00 and set the owned slot #3 to match C5. We now have five final slot values.
Working with CHICO we can set the owned #0 slot so its XOR with slots #4 (17) and #6 (00) produces 6B; the slot is set to 7C, and we have six final slot values.
The process is similar for ZEPPO (setting slot #2, taking into account the already set #4 and #6 slots), then GROUCHO (setting its owned slot #7 considering the values for slots #0 and #3), and finally BROTHERS (setting its owned slot #5, the last one).

How is this implemented? Let's analyze the rest of the code for createXorFilter.

const createXorFilter = (items, eps = EPSILON) => {

  // calculation of p and s, shown earlier, snipped out

➊const MAX_SEEDS = 1000;
  for (let seed = 0; seed < MAX_SEEDS; seed++) {
➋  const indices = items.map((item) =>
      indicesOf(item, seed, s)
    );

➌  const itemCounts = new Uint32Array(3 * s);
    const xors = new Uint32Array(3 * s);

➍  indices.forEach((itemIndices, itemIndex) => {
      itemIndices.forEach((index) => {
        itemCounts[index]++;
        xors[index] ^= itemIndex;
      });
    });

➎  const queue = [];
    itemCounts.forEach((count, index) => {
      if (count === 1) {
        queue.push(index);
      }
    });

➏  const peeled = [];
    for (let head = 0; head < queue.length; head++) {
      const index = queue[head];
➐    if (itemCounts[index] === 1) {
        const itemIndex = xors[index];
        peeled.push([itemIndex, index]);
        for (const other of indices[itemIndex]) {
          itemCounts[other]--;
          xors[other] ^= itemIndex;
          if (itemCounts[other] === 1) {
            queue.push(other);
          }
        }
      }
    }

➑  if (peeled.length === items.length) {
      const b = new Uint32Array(3 * s);
      const mask = (1 << p) - 1;
➒    for (let j = peeled.length - 1; j >= 0; j--) {
        const [itemIndex, index] = peeled[j];
        let fp = fingerprintOf(items[itemIndex], p);
        indices[itemIndex].forEach((i) => {
          fp ^= b[i];
        });
➓      b[index] = (fp ^ b[index]) & mask;
      }

      return { p, seed, s, b };
    }
  }

  throw new Error(
    "XOR filter: could not construct a peelable filter"
  );
};

There's one issue ➊ we haven't discussed yet. As we described the "peeling" algorithm, it works as long as you can find columns used by only one remaining yet-unpeeled item… but is this guaranteed? The fact is, if you have bad luck, two different items could hash to the same three slots, and that would stop the algorithm cold. There's a simple solution that will almost certainly work: use a seed to calculate the three hashes, and if the algorithm fails, switch to another seed and try again. Obviously, we cannot keep attempting this, so some limit has to be set; if after MAX_SEEDS different seeds we keep failing, we'll give up.

What do we do in each attempt? The indices array ➋ will just store the three hashes for each item. The itemCounts array ➌ will count how many items use that slot, and the xors array stores the XOR of all the item indices that use the slot; as items get peeled away, their indices are XORed out, so when the count reaches 1, xors will have the index of the item that will own the slot.

We will push indices of the slots with just one user into the queue array ➎ and we'll start the "peeling" algorithm. We'll track the peeled items in the peeled array ➏ and start assigning values. The test at ➐ matters: we queue elements that use a single slot, but when we "remove" its row, we decrement counts in three buckets, so another bucket's count may drop from 1 to 0. When decrementing slot counts, if some other slot ends up associated with just one item, we push it into the queue for future processing.

Final processing ➑ starts by testing whether every item was peeled (and, if not, we loop again with another seed) and computes masks. We go down the peeled list in reverse order ➒ and do calculations so the XOR of the three slots matches the item's fingerprint; the key line is the assignment to b[index] ➓.

Bye for now! In the next article in the series, we will look at Ribbon Filters, which work similarly to XOR Filters but with even less memory overhead.

Want to get the book?

Part 11: Cuckoo Filters - Operations

Federico Kereki — Sun, 25 Oct 2026 13:01:12 +0000

In the previous article, we saw how to size and create a Cuckoo Filter. Here we'll see how to do searches, add new values, and remove old ones.

Adding a value to a Cuckoo Filter

For a CF, searches and removals are simple and depend entirely on the addition logic, so it makes sense to start there. Let's assume we already have a CF with some previously stored fingerprints. We are using 4-bit fingerprints, so a single hex digit (1–9, A-F) is enough. The CF has 8 buckets, each with 2 slots.

First, consider the easy case in Figure 11½–18. We want to add GROUCHO; we calculate its fingerprint (A) and indices (2 and 7), and both buckets have free space, so we can add the fingerprint in either bucket.

Figure 11½–18: When both buckets are available for an addition, we can pick either.

For a second case (see Figure 11½–19) suppose HARPO should go in buckets 2 or 1. In this case, bucket 2 is full, but bucket 1 has space, so we have no choice but to add the new fingerprint there.

Figure 11½–19: As long as at least one of the picked buckets has some free slot, additions are immediate

Finally (Figure 11½–20) let's go for the difficult case. CHICO should go in either bucket 3 or 5, but both are full. In this case, we randomly pick a value in one bucket (here, the 9 in bucket 5), place CHICO's fingerprint there, and relocate the kicked-out value. How do we do this? Given the fingerprint (9) and the bucket (5) we can calculate that the companion bucket would be 7. The bucket has free space, so the 9 goes there and we are done.

Figure 11½–20: If both buckets are full, we kick a value out to make space; this may end in a whole run of "kicks"

But what happens if bucket 7 is also full? That starts a sequence of "kicking out" steps, in which you again pick a value from the bucket, use its (now free) space, and relocate the kicked-out value to its alternative bucket. However, there's a possible issue: this sequence might get into a loop, so after a maximum number of attempts we have to accept that we cannot add the value and roll back all our changes. (But why? See question 11½–10.)

Let's now get to coding. We'll need some auxiliary functions to calculate fingerprints, indices, hashes, etc.

➊ const fingerprintOf = (filter, item) =>
  hashWithSeed(item, 0) & ((1 << filter.p) - 1) || 1;

➋ const hashBucket = (filter, item, seed) =>
  hashWithSeed(item, seed) % filter.b;

➌ const index1 = (filter, item) => hashBucket(filter, item, 1);

➍ const index2 = (filter, index1, fingerprint) =>
  index1 ^ hashBucket(filter, fingerprint, 2);

➎ const twoBuckets = (filter, item) => {
  const fingerprint = fingerprintOf(filter, item);
  const i1 = index1(filter, item);
  return {
    fingerprint,
    indices: [i1, index2(filter, i1, fingerprint)]
  };
};

To compute a fingerprint ➊ we use the same hashWithSeed function we've been using, masking to get just p bits; should the fingerprint be zero, we return 1 instead. (See question 11½–9 for an alternative.) The hashBucket function ➋ is auxiliary; given a number and a seed, it uses hashing and the modulus operation to produce a bucket number. The index functions ➌ ➍ apply the formulae we described to produce both indices. For maximum independence, we use different seeds for the hashes in each calculation. Finally ➎ twoBuckets just uses the first four functions to return an object with the fingerprint and the two indices.

Now we can add a value to the CF.

➊const MAX_KICKS = 500;

const add = (filter, item) => {
➋if (filter.c + 1 > filter.n) {
    throw new Error("Cuckoo filter load limit reached");
  }

➌const { fingerprint, indices } = twoBuckets(filter, item);
  for (const index of indices) {
    if (filter.buckets[index].length < filter.s) {
      filter.buckets[index].push(fingerprint);
      filter.c++;
      return true;
    }
  }

➍const originalBuckets = new Map();

➎let index = singlePickAll(indices);
➏let carriedFingerprint = fingerprint;
  for (let kick = 0; kick < MAX_KICKS; kick++) {
    // Save the original bucket if it hasn't been saved yet.
➐  const bucket = filter.buckets[index];
    if (!originalBuckets.has(index)) {
      originalBuckets.set(index, bucket.slice());
    }

➑  const slot = randomInt(0, bucket.length);
    [carriedFingerprint, bucket[slot]] = [
      bucket[slot],
      carriedFingerprint
    ];
    index = index2(filter, index, carriedFingerprint);

➒  if (filter.buckets[index].length < filter.s) {
      filter.buckets[index].push(carriedFingerprint);
      filter.c++;
      return true;
    }
  }

➓for (const [bucketIndex, originalBucket] of originalBuckets) {
    filter.buckets[bucketIndex].splice(
      0,
      filter.buckets[bucketIndex].length,
      ...originalBucket
    );
  }
  return false;
};

To detect "kick out loops", we'll have ➊ a fixed upper limit on how many times we'll attempt the removal process. For starters ➋ we check if the CF is loaded enough; if so, we reject the addition. Then ➌ we calculate the fingerprint and indices for the value, and if there's free space in any corresponding bucket, we put the fingerprint there, and we're done. We may have to restore buckets later ➍ so we'll use the originalBuckets map to store the original versions of any buckets we may modify.

At this point ➎ we know we'll have to kick out some value, so we use the singlePickAll function we developed in the Sampling section of Chapter 8 in the book; it takes a whole array as input and randomly picks a value, so index points to one of the two buckets for the value. The carriedFingerprint variable ➏ will represent the kicked-out value in the loop we'll do. If we hadn't yet modified the bucket ➐ we'll save it into the originalBuckets map so we can later restore it, if need be.

We want to remove a random fingerprint from the bucket; we use the randomInt function from the Choosing Numbers Randomly section of Chapter 8 to select some slot ➑ and we use it for the value we were moving. If there is space in the slot ➒ we are done; otherwise, the loop will continue trying to relocate the value in carriedFingerprint. Should the loop finish because of the iterations limit ➓ we'll restore all buckets from the map, so they remain as they were.

We now know how to add values to a CF; we can move on to searching, which will need much less code, as we'll see.

Searching a Cuckoo Filter

Let's start by reviewing some examples. In Figure 11½–21 we see the search for CHICO: we calculate the two indices and check whether the fingerprint is at either. We find it, so the search was positive.

Figure 11½–21: A search for an inserted value is successful, for its fingerprint will be at one of two buckets

Now, we could look for ZEPPO; see Figure 11½–22. Why. We calculate the fingerprint and indices, but in this case the fingerprint isn't found in any bucket; we know ZEPPO was never stored, and the search is negative.

Figure 11½–22: A search fails if the fingerprint is not at any of the value's two buckets

Finally, we can also have false positives; see Figure 11½–23. Imagine that when looking for GUMMO, its fingerprint is A (the same as GROUCHO's) and its first index is 7. Calculating the second index would produce 2; both indices match GROUCHO's, and we'd wrongly believe GUMMO had been inserted.

Figure 11½–23: There's always the possibility that two different values will produce the same fingerprint and indices, and that would produce a false positive

Now we can get to actual code, which is quite short.

const find = (filter, item) => {
➊ const {
    fingerprint,
    indices: [i1, i2]
  } = twoBuckets(filter, item);

➋ return (
    filter.buckets[i1].includes(fingerprint) ||
    filter.buckets[i2].includes(fingerprint)
  );
};

This logic (just two lines!) is straightforward. We first ➊ calculate the fingerprint and indices, then ➋ check whether the former is included in either bucket; very direct! (See question 11½–11 for an alternative way to write this code.)

Now we just need to remove a value from a CF; this will take only a few more lines than a search.

Removing a value from a Cuckoo Filter

Since we already know how to find a value in a CF, removal is really simple.

const remove = (filter, item) => {
➊ const { fingerprint, indices } = twoBuckets(filter, item);
➋ for (const index of indices) {
    const slot = filter.buckets[index].indexOf(fingerprint);
➌  if (slot !== -1) {
      filter.buckets[index].splice(slot, 1);
      filter.c--;
      return true;
    }
  }
  return false;
};

As in find we start ➊ by calculating the fingerprint and the bucket indices. Then ➋ we check both buckets; if the fingerprint is found at any of them ➌ we just remove it, and we're done.

Bye for now! In the next article in the series, we will introduce XOR Filters, which trade dynamic updates flexibility for maximum speed and lower memory requirements.

Questions

11½–9. If at first you fail… If, when calculating the fingerprint, the hash function returns a zero, would this alternative work? Why or why not?

const fingerprintOf = (filter, item) =>
  hashWithSeed(item, 0) & ((1 << filter.p) - 1) || 
  hashWithSeed(item, 4) & ((1 << filter.p) - 1);

11½–10. Let it Be. Why do we need to restore the buckets to their original values? Would the CF be broken if we didn't do that?

11½–11. Some like it short. Just for variety, can you rewrite find to use the .some method?

Want to get the book?

Part 10: Cuckoo Filters - Creation

Federico Kereki — Sat, 24 Oct 2026 12:05:44 +0000

In previous articles in this series we saw several versions of Bloom Filters and then Counting Filters and Quotient Filters, which allow deletions. Here we'll see a new structure, Cuckoo Filters, with better performance and lower storage requirements.

Cuckoo Filters

In previous sections, we started with Bloom Filters, which don't allow deletions; we then touched on Counting Bloom Filters to address that, and eventually moved to Quotient Filters without that restriction. We'll now look at Cuckoo Filters, introduced in 2014 by Bin Fan, David Andersen, Michael Kaminsky, and Michael Mitzenmacher in their "Cuckoo Filter: Practically Better Than Bloom" paper.

This new filter beats Quotient Filters in performance and space. It uses a structure of buckets, each with a fixed number of available slots, where fingerprints are stored. Each value to be stored is represented by a fingerprint and is associated with two bucket indices; the value may be stored in a free slot of either bucket. If both buckets are full, the filter kicks out an existing value (which must then move to its alternate bucket) and stores the new value in its place. This behavior reminds us of some cuckoo birds, which are brood parasites: a female lays her egg in another bird's nest, and when the cuckoo chick hatches, it instinctively pushes the host's eggs or chicks out. The newcomer takes the slot by evicting whatever was there.

How Cuckoo Filters Work

A CF has b buckets; to allow using efficient binary operators, b is a power of 2. Each bucket has s slots, and as in a QF, we won't store values in the slots; just fingerprints. We won't accept zero as a fingerprint; that will represent an empty slot. Fingerprints in a bucket will not be in any particular order. For each value to be included in a CF, we will compute three results:

fp, a fingerprint, p bits long; p is chosen to achieve a low false-positive rate.
i1, a first index, calculated as hash(value) - we assume this returns a valid bucket number.
i2, a second index, calculated as i1 XOR hash(fp), which must also be a valid bucket number.

Why are indices calculated this way? The key is that given the fp fingerprint and one index, you can find the other one by doing an XOR with hash(fp):

Given i1, the calculation produces i1 XOR hash(fp), which is i2 by definition.
Given i2, we calculate i1 XOR hash(fp) XOR hash(fp) and since for all values Y XOR Y=0 and X XOR 0 = X the result is just i1.

How does this work? If we are searching for a value, we need to calculate its fingerprint and indices, then check both buckets to see whether the fingerprint is in either. If we don't find it, the answer is a definite "no; not present"; if we do, the answer is a "may be present", as with other filters.

Removing a value is equally easy; if you search for the value and find it, you just remove it from the corresponding bucket. The same considerations we saw for previous filters, such as the possibility of removing the wrong value, remain unchanged.

Finally, how do additions work? This is where things get interesting. We calculate the fingerprint and both indices. If either bucket has space, we add the fingerprint there, and we're done. If not, we randomly pick a slot and put the new fingerprint there. We will calculate the other index for the removed value and attempt to place it in the other bucket. If there's space, we store it; if not, we repeat the "push" by picking a random value from that slot, and so on. This kicking process could enter a loop; we will consider that later, when we see actual code.

Creating a Cuckoo Filter

We expect to store n items in b buckets (b must be a power of 2) with s slots each, and we want a maximum load factor of α. The original paper suggests s=4 for probabilistic reasons (it could go up to 8) so we'll go with that. The buckets provide bs slots in total, so α = n/bs. Accordingly, we want b to be a power of 2 at least as large as n/(sα).

Then, we need to determine the fingerprint length in bits, p. A lookup checks two candidate buckets, each with at most s fingerprints. If fingerprints are uniformly distributed, the false-positive probability is approximately ε ≈ 2_s_/2^p, so p should be ⌈log₂(2_s_/ε)⌉.

We can now show the CF creation code.

const EPSILON = 0.01;
➊ const ALPHA = 0.9;

const createCuckooFilter = (n, eps = EPSILON) => {
➋const s = 4;

➌const b = nextPowerOfTwo(n / (s * ALPHA));

➍const p = Math.ceil(Math.log2((2 * s) / eps));
  if (p > 24) {
    throw new Error(
      "Cuckoo filter: epsilon exceeds 24-bit fingerprint limit"
    );
  }

➎return {
    n,
    b,
    s,
    p,
    c: 0,
    buckets: Array.from({ length: b }, () => [])
  };
};

The recommendations for α are between 0.90 and 0.95; here ➊ we chose the former. Similarly, for slots ➋ the usual value for s is 4; higher values are possible but not recommended. We use the formulae we derived for b ➌ and p ➍; we added an extra check so we don't require too large fingerprints. (As an aside, we could also add a check to make sure that b s-sized arrays do not require too much space.) We finally ➎ return an object also including c, the running count of elements in the CF, and buckets, the buckets themselves. (Check question 11½–5 in a previous article to avoid a big mistake.) Buckets just have empty arrays to begin with, but when adding new values we'll make sure they do not go past s slots.

Bye for now! In the next article in the series, we will see how to search and update a Cuckoo Filter.

Want to get the book?

Part 9: Quotient Filters - Removing Values

Federico Kereki — Mon, 19 Oct 2026 14:50:33 +0000

In the previous article of this series, we saw how to add values to a Quotient Filter; now let's see how to remove some.

Removing a Value from a Quotient Filter - Examples

Let's see how to remove values from a QF. Interestingly, the examples we saw for additions in the previous sections will work now for removals, but in reverse! (See question 11½–8 for more on this.) We will just go over the earlier examples again, but in reverse. First, let's remove A for q=2.

Figure 11½–15: Removing a value at the end of a run and a cluster

After checking that the run exists for q=2 (isOcc is set) we find the start of the run. As isShifted is not set, the run begins right there. The next slot is empty (isCont is not set) so the run ends after one element, and there is nothing to shift. To remove the value, we clear the remainder, and reset isOcc; the other metadata bits are already unset.

Now let's see how we'd remove H in the middle of a cluster. Also, the value is the only one in its run; we'll see an example with a longer run after this one.

Figure 11½–16: Removing a value from the start of a run, at the middle of a cluster

After checking that the run for q=6 exists, we find the corresponding cluster; occupied quotients from slot 4 (the beginning of the cluster) up to 6 are 4, 5, and 6, and the runs start at positions 4, 8, and 10. We scan the run for q=6, find the match, and since slot 11 has isCont not set, we just remove H by shigetting to the main logic, let's seefting the rest of the cluster leftward. As the run had a single element, we clear isOcc.

For a final case, let's remove something from the middle of a run; we want to delete the value for q=5 and remainder C. (Remember, we deliberately had a repeated remainder to show that remainders are not unique.) The following figure shows the case.
isShifted

" width="800" height="540">
Figure 11½–17: Removing a value from the middle of a run

Here we proceed the same way, and after finding the run and the remainder in it, we shift the remaining cluster elements left. Here the run still has other values (B and D) so isOcc remains set. After the shift, the last slot in the cluster becomes empty. The removed element wasn't the head of the run, so no new head gets isCont unset. Had B been removed instead, C would have become the head of the run, with isCont unset.

Removing a Value from a Quotient Filter - Implementation

In essence, removing a value is similar to adding one. First, verify whether the value is in the QF; if it is, shift all following items backward, possibly fixing some metadata bits. Before the main logic, let's look at an auxiliary function, clusterRunQuotients, which we'll use later. This function receives the first slot of a cluster and returns the home slots (quotients) of all the runs stored in that cluster, in table order.

const clusterRunQuotients = (qf, slot) => {
➊const quots = [];

➋for (
    let is1stPass = true;
    !isSlotEmpty(qf, slot) &&
    (is1stPass || qf.slots[slot].isShifted);
➌  slot = wrapSlot(qf, slot + 1), is1stPass = false
  ) {
➍  if (qf.slots[slot].isOcc) {
      quots.push(slot);
    }
  }

  return quots;
};

The quots array ➊ will collect the quotients found when starting from slot. We have a loop (which I wrote using for(...) just for variety; a while would also have done well) that starts ➋ at the run's first slot and moves forward. The loop continues only while the current slot is not empty (because a cluster is a contiguous group of used slots) and it is either the first slot, or the slot is shifted; an unshifted entry sits in its own home slot, beginning a new cluster. After the test ➌ we advance and reset the is1stPass flag. In the loop ➍ we push the slot number whenever we find isOcc set.

When we are done, the k-th element in the returned array is the home slot for the k-th run in the cluster; we'll use this to know which run each shifted entry belongs to. Now we can get to the main remove code.

const remove = (qf, item) => {
➊const [quot, rem] = fingerprintOf(qf, item);

➋if (!qf.slots[quot].isOcc) {
    return false;
  }

➌const clusterStart = findClusterStart(qf, quot);
  const runStart = locateRun(qf, quot);

  let target = runStart;

➍for (;;) {
    if (
      isSlotEmpty(qf, target) ||
      (target !== runStart && !qf.slots[target].isCont) ||
      qf.slots[target].rem > rem
    ) {
      return false;
    }

➎  if (qf.slots[target].rem === rem) {
      break;
    }
    target = wrapSlot(qf, target + 1);
  }

➏const wasRunStart = target === runStart;
  const nextSlot = wrapSlot(qf, target + 1);
  const hasMoreOfSameRun =
    !isSlotEmpty(qf, nextSlot) && qf.slots[nextSlot].isCont;

➐const runQuotients = clusterRunQuotients(qf, clusterStart);
  let currentRunIndex = runQuotients.indexOf(quot);

➑if (wasRunStart && !hasMoreOfSameRun) {
    qf.slots[quot].isOcc = false;
  }

➒shiftLeftAndRemove(
    qf,
    target,
    runQuotients,
    currentRunIndex,
    wasRunStart,
    hasMoreOfSameRun
  );

  return true;
};

The goal of the code is to delete one copy of an item's remainder from its run, then close the gap by sliding the rest of the cluster one slot to the left. We find the quotient and remainder ➊ and if the slot is empty ➋ we know that the item cannot be in the filter, so there's nothing to do. We find the start of the cluster ➌ and the start of the run for the quot run. We scan the run from its beginning ➍ looking for the remainder. We know the search was unsuccessful in three cases: if the slot is empty, if we've entered another run, or if the stored remainder is greater than the one we seek, so ours cannot appear later. An equal remainder ➎ means we found the slot to delete, called target.

We record ➏ two facts about the deleted element's situation, which we'll need to decide whether some metadata bits need fixing: whether it was the first element of its run, and whether the next slot continues the same run. Next ➐ runQuotients is the ordered list of home slots of all runs in the cluster, and currentRunIndex is the position of our run in it. During the shift, this lets us work out whether each moved element ends up in its home slot. It is computed before anything changes. If we are deleting the only element in the run ➑ the run disappears, so the home slot's isOcc bit is cleared. Finally ➒ shiftLeftAndRemove closes the gap, and we return true.

Doing the shifting and bit handling is in a separate function, as for add.

const shiftLeftAndRemove = (
  qf,
  slot,
  runQuotients,
  currentRunIndex,
  wasRunStart,
  hasMoreOfSameRun
) => {
  let is1stIteration = true;
  for (;;) {
    const next = wrapSlot(qf, slot + 1);

➊  if (isSlotEmpty(qf, next) || !qf.slots[next].isShifted) {
➋    qf.slots[slot].rem = 0;
      qf.slots[slot].isOcc = false;
      qf.slots[slot].isCont = false;
      qf.slots[slot].isShifted = false;
      qf.c--;
      return;
    }

➌  if (!qf.slots[next].isCont) {
      currentRunIndex++;
    }

➍  let continuationToWrite = qf.slots[next].isCont;
    if (is1stIteration && wasRunStart && hasMoreOfSameRun) {
      continuationToWrite = false;
    }

➎  qf.slots[slot].rem = qf.slots[next].rem;
    qf.slots[slot].isCont = continuationToWrite;

    if (!continuationToWrite) {
      qf.slots[slot].isShifted =
        slot !== runQuotients[currentRunIndex];
    } else {
      qf.slots[slot].isShifted = true;
    }

➏  slot = next;
    is1stIteration = false;
  }
};

This function overwrites the deleted slot with its successor, then repeats with that successor's slot, and so on down the cluster. Before pulling the next slot in ➊ we check whether it should move. If it is empty, or its isShifted bit is false, it is in its own home slot and marks the start of a new cluster, so it must not move. The current slot is then the last one of the shifted tail. The last slot is wiped ➋ by clearing all three flag bits, and the item count qf.c is decremented. The isOcc bit is also cleared here, which is safe because no run can have its home at a slot whose successor is the start of a new cluster. If the successor is not a continuation ➌ it begins a new run, so we advance currentRunIndex to that run's home slot. When the deleted element was the only one in its run, this also skips past the vanished run correctly. We decide the continuation bit to write ➍; normally it is the successor's own, but the exception is the very first iteration when we deleted a run start that has more elements: the successor becomes the new first element of the run, so its isCont is forced to false. The remainder and continuation bit are copied into the current slot ➎ and isShifted is recomputed: a continuation element is always shifted, and a run-start element is shifted only if its new slot differs from its run's home slot, since moving left may put it exactly at home. Finally ➏ the loop moves on to the slot we just copied from, and the first-iteration special case no longer applies.

We're done! We can move on to a better-performing filter, Cuckoo Filters, which are also related to hash tables with buckets, as we'll see.

Bye for now! In the next article in the series, we will study Cuckoo Filters, which have some performance advantages in terms of speed and memory needs.

Questions

11½–8. It all comes out in the wash. For a QF, does the order in which we add values affect its final configuration? What happens if we also consider removals?

Want to get the book?

Part 8: Quotient Filters - Adding Values

Federico Kereki — Sun, 18 Oct 2026 17:10:55 +0000

In the previous article of this series, we saw how to create and search a Quotient Filter; now let's see how to add values. This article will be longer than usual, but that's because we'll have plenty of code; no way around that!

Adding a value to a Quotient Filter - Examples

We can now see how to add a value to a QF. First, let's see a few examples so we can better understand the logic we'll write. For clarity, in all cases we'll start with the setup we saw in previous parts, and show a single update.

The first case is the simplest one; see figure 11½–12. We add a value with a quotient, A, that hasn't appeared yet, and its slot is empty. In that case, we just occupy the slot and set its isOcc bit to 1; isCont and isShifted stay at 0 because A is the first element of a run and it's in its home slot. The figure below shows this situation; involved items have thick borders, and changed values have a grey background.

Figure 11½–12: The simplest addition is when the home slot is empty, available.

What happens if we add a new run but the slot is occupied? Figure 11½–13 shows this situation; the new remainder, H, is for q=6.

Figure 11½–13: Here we add a new run not at its home slot, and have to displace other items.

In this case, we needed several changes:

isOcc becomes 1 at slot #6, because now we have one run for that quotient.
H is stored at slot 10, right after the end of the run for q=5 and before the beginning of the run for q=7. It has isCont set to 0 because it starts a run, and isShifted set to 1 because it's not at the home slot.
elements after H in the same cluster are moved right; this involves C, F, and H, and their values for rem, isCont, and isShifted are displaced.

Let's just see one more example, adding something somewhere in an existing run; in this case, we'll add remainder C to q=5. (And, yes, remember the same remainder may appear for different quotients; I wanted to specifically show a case of this.) Figure 11½–14 shows how it would go.

Figure 11½–14: Adding a new value to an existing run.

In this case:

isOcc[5] doesn't change because it was already 1
the new value goes between B and D so the former stays in place; the head of the run doesn't change in this example
all the rest of the items in the cluster starting at D onwards move forward (with their isCont and isShifted bits unchanged) to open space for C as a continuation (isCont=1) and displaced (isShifted=1)

Inserting the value at the end of a run (say, remainder I for q=5) would have been very similar. Adding remainder W to q=15 would also work in the same way, except for the wrapping around.

In essence, the examples above cover all the possibilities; we can now move on to actual JavaScript code.

Adding a value to a Quotient Filter - Implementation

Now, let's get to the code. As we saw earlier, the issue is determining where the new value should fit, possibly displacing other items forward to make space. The code is a bit longish; see below.

const add = (qf, item) => {
➊if (qf.c + 1 > qf.s * ALPHA) {
    throw new Error("Quotient filter load limit reached");
  }

➋const [quot, rem] = fingerprintOf(qf, item);

➌if (isSlotEmpty(qf, quot)) {
    const slot = qf.slots[quot];
    slot.rem = rem;
    slot.isOcc = true;
    qf.c++;
    return;
  }

➍const runAlreadyExists = qf.slots[quot].isOcc;
  qf.slots[quot].isOcc = true;
➎const runStart = locateRun(qf, quot);

  let insertAt;
  let is1stOfRun;
  if (runAlreadyExists) {
    let slot = runStart;

➏  while (true) {
      if (
➐      isSlotEmpty(qf, slot) ||
        (slot !== runStart && !qf.slots[slot].isCont) ||
        qf.slots[slot].rem >= rem
      ) {
        break;
      }

      slot = wrapSlot(qf, slot + 1);
    }

➑  insertAt = slot;
    is1stOfRun = insertAt === runStart;
  } else {
➒  insertAt = runStart;
    is1stOfRun = true;
  }

➓shiftRightAndInsert(
    qf,
    insertAt,
    rem,
    !is1stOfRun,
    insertAt !== quot,
    runAlreadyExists && is1stOfRun
  );
};

As we mentioned earlier, we don't want the QF to get too full, so we do not allow an insertion ➊ if the table load factor would become too high; this bounds how long runs and clusters get. (Also, if the table could be full, the algorithms we would need extra checks to avoid infinite loops.)

After that check ➋ we find the fingerprint (quotient and remainder) for the value, and check for the "fast path". If the home slot is empty ➌ we just store the remainder there, set the metadata bits, and we're done! Otherwise, the canonical slot is in use, either by this quotient's run or by another entry shifted in from elsewhere.

The slot's isOcc flag says whether a run for this quotient already exists ➍. That value is saved in runAlreadyExists before the flag is forced to true, because the quotient will have a run after this insertion either way, and the old value is still needed below. Now ➎ we find the slot where the run for quot starts. If the run doesn't exist yet, we get the slot where the new run should begin. We now have to find where the new remainder should go ➏ keeping its run in ascending order. We will be done in this search ➐ when either:

the slot is empty, so the run ended exactly at the edge of the occupied cluster, and the item can go there with nothing to move.
the slot is not the run's start and is not a continuation: it belongs to the next run, so the current run has ended, and the item goes at its end.
the stored remainder is greater than or equal to the new one, so we know where to insert it. (See question 11½–7 for more on this.)

In any of these cases ➑ insertAt is the final slot. Here, is1stOfRun is true only when the insertion point is the run's first slot, meaning the new remainder is the smallest in the run. If the item landed later in the run or just past its end, it is not the first. If no run existed ➒ the new run starts instead at the location from ➎, and the item is by definition its first member.

The final step ➓ shifts slots right to finish the work. The shiftRightAndInsert function receives the remainder and three flags, and does the needed insertion:

!is1stOfRun becomes the continuation bit. Anything that is not the first of its run is a continuation.
insertAt !== quot becomes the shifted bit. The item is shifted if it ends up away from its canonical slot.
runAlreadyExists && is1stOfRun is the "force next continuation" flag. It applies when the new item becomes the head of an existing run. The old head, which is displaced one slot to the right, must then be marked as a continuation. If the run is new, this is false, and whatever is displaced keeps its status, since it belongs to a different run.

We're almost done! The shiftRightAndInsert function is also a bit longish. Its job is to shift elements forward, making space to add the new remainder.

const shiftRightAndInsert = (
  qf,
  slot,
  rem,
  continuationFlag,
  shiftedFlag,
  forceNextContinuation
) => {
➊let carryRem = rem;
  let carryContinuation = continuationFlag;
  let carryShifted = shiftedFlag;
  let is1stIteration = true;

➋for (;;) {
➌  if (isSlotEmpty(qf, slot)) {
      qf.slots[slot].rem = carryRem;
      qf.slots[slot].isCont = carryContinuation;
      qf.slots[slot].isShifted = carryShifted;
➍    qf.c++;
      return;
    }

➎  const displacedRem = qf.slots[slot].rem;
    let displacedContinuation = qf.slots[slot].isCont;

➏  if (is1stIteration && forceNextContinuation) {
      displacedContinuation = true;
    }

➐  qf.slots[slot].rem = carryRem;
    qf.slots[slot].isCont = carryContinuation;
    qf.slots[slot].isShifted = carryShifted;

➑  carryRem = displacedRem;
    carryContinuation = displacedContinuation;
    carryShifted = true;

➒  slot = wrapSlot(qf, slot + 1);
    is1stIteration = false;
  }
};

The function works like a bucket brigade; at any moment ➊ it holds one "carried" entry: a remainder plus its continuation and shifted metadata bits. Initially, the carried entry is the new item, plus the bits that were determined by add, and is1stIteration is needed later for a special case. A forever loop ➋ starts, which ends only ➌ when the carried entry lands in an empty slot and ➍ the element count is updated.

When moving forward, if an occupied slot is found ➎ its current remainder and continuation bit are saved before being overwritten. This is the entry that will move one slot right. On the first iteration only, if forceNextContinuation is set ➏ the displaced entry's continuation bit is forced to true. This covers the case when a new item takes over the head of an existing run, while the old head becomes the second element of the run, a continuation. (Later displaced entries keep their own continuation bits, since their position within their runs doesn't change.) The slot ➐ receives the carried remainder and metadata. (For the first slot these are the values chosen by add, and for later slots they are the values of the displaced entry.) Then ➑ the displaced entry becomes the new carried entry, always having its shifted bit to true, because it gets moved from its original place, which can no longer be its canonical slot. Finally ➒ the loop advances to the next slot, clearing the first iteration flag so the rule at ➏ won't fire again.

Bye for now! In the next article in the series, we will see how to remove values from a Quotient Filter.

Questions

11½–7. Add it again, Sam. What happens if we try to add the same value twice? How do we detect the case; would a previous search do?

Want to get the book?

Part 7: Quotient Filters - Creating and Searching

Federico Kereki — Fri, 16 Oct 2026 11:39:29 +0000

In the previous article of this series, we saw how a Quotient Filter is used. Here we'll see how to size and search those filters, with actual code.

Creating a Quotient Filter

Before we look at the code for creating a QF, let's work out what its parameters should be. Suppose we want to add n values to a QF with an α false-positive rate below ε and a load factor below α. (Why the latter? A QF is similar to a hash table in some ways, and the higher the load factor, the slower all operations are. We might want α below 0.75, for example.) How should we size the QF?

We need n/s < α and s = 2^q because we want the table length to be a power of 2. This leads to q = ⌈log₂(n/α)⌉, our first result.
A query for a key that isn't in the set gives a false positive only if its p-bit fingerprint matches one of the n stored fingerprints. For a uniform hash, each stored key matches with probability 2^‑p. Since we want this to be lower than ε, p = ⌈log₂(n/α)⌉ and then r = p‑q.

Given these results, we can now show how to create a QF.

const EPSILON = 0.01;
const ALPHA = 0.75;

const createQuotientFilter = (n, eps = EPSILON) => {
➊const p = Math.ceil(Math.log2(n / eps));
  const q = Math.ceil(Math.log2(n / ALPHA));
  const r = p - q;
  const s = 1 << q;
  const c = 0;    // number of values in the QF

➋return {
    p,
    q,
    r,
    s,
    c,
➌  slots: Array.from({ length: s }, () => ({
      rem: 0,
      isOcc: false,
      isCont: false,
      isShifted: false
    }))
  };
};

First, we do the calculations ➊ as shown before; a good idea is to add defensive checks to avoid wrong parameters. For us ➋ a QF will be an object with all the dimensions ( p, q, r, and s ) and c to count how many values are in the QF; we will want to avoid overloading the structure with too many values. Finally ➌ the slots array includes the rem field to store the remainders, and the three metadata bits we described previously. (See question 11½–5 for a possible, but incorrect, way to simplify the code.)

We will also introduce the fingerprint function, which depends on the calculated values for p, q, and r. We will use the hashWithSeed function from earlier articles to produce an array with quotient and remainder.

const fingerprintOf = (qf, item) => {
  const hash = hashWithSeed(String(item), 0);
  return [
➊ (hash & ((1 << qf.p) - 1)) >>> qf.r,
➋  hash & ((1 << qf.r) - 1)
  ];
};

The bitwise operations simplify the work:

the quotient is found ➊ by first masking out all bits except the rightmost p ones, and then shifting right to drop r bits, leaving just q bits, and
the remainder is found ➋ by masking out all bits except the rightmost r ones.

We can now create a QF; let's work out how to search it, as described in the previous article.

Searching a Quotient Filter

Let's see the code to find a value. To make the logic clearer, we'll be using a few auxiliary functions that will also come in handy for other operations on a QF.

➊ const wrapSlot = (qf, slot) => (slot + qf.s) % qf.s;

➋ const isSlotEmpty = (qf, slot) =>
  !qf.slots[slot].isOcc &&
  !qf.slots[slot].isCont &&
  !qf.slots[slot].isShifted;

First ➊ we need a function to avoid going out of the array bounds when moving forwards or backward, taking into account that we are wrapping around; the calculation used takes any index (even -1) and forces it into the correct range. We will also write a function to determine if a slot is totally empty ➋ by checking if all its metadata bits are unset. With these two functions under our belt, we can now do a search.

const find = (qf, item) => {
➊  const [quot, rem] = fingerprintOf(qf, item);

➋  if (!qf.slots[quot].isOcc) {
      return false;
    }

➌  const runStart = locateRun(qf, quot);
    let slot = runStart;
➍  while (true) {
      if (
➎      isSlotEmpty(qf, slot) ||
➏      (slot !== runStart && !qf.slots[slot].isCont) ||
➐      qf.slots[slot].rem > rem
      ) {
      return false;

➑  } else if (qf.slots[slot].rem === rem) {
      return true;

    } else {
➒    slot = wrapSlot(qf, slot + 1);
    }
  }
};

To start the search ➊ we find the fingerprint for the sought value, a quotient and remainder, and if there were no values for that quotient ➋ we know the value isn't present. We use an auxiliary runStart function ➌ to find the first slot in the run that contains the quotient; we'll see it below. After that ➍ we start walking forward. If we reach an empty slot ➎ we walk past the end of the current run ➏, or we are at the right run but exceeding the sought remainder ➐ then the search fails. (For an important detail, see question 11½–6.) If we find the expected remainder ➑ the search succeeds, and in other cases ➒ we just keep advancing.

In the add function, we ensure the table is never 100% full; otherwise, we'd need checks to avoid looping back to the start of the search. (In fact, we'll force its load factor to always be below α to ensure good performance.) Now, let's see the locateRun function.

 ➊const findClusterStart = (qf, slot) => {
  while (qf.slots[slot].isShifted) {
    slot = wrapSlot(qf, slot - 1);
  }
  return slot;
};

const locateRun = (qf, quot) => {
➋let clusterStart = findClusterStart(qf, quot);
  let runNumber = 0;
  let slot = clusterStart;
  while (true) {
➌  if (qf.slots[slot].isOcc) runNumber++;
➍  if (slot === quot) break;
➎  slot = wrapSlot(qf, slot + 1);
  }

➏let runStart = clusterStart;
  for (
    let currentRun = 1;
    currentRun < runNumber;
    currentRun++
  ) {
    do {
➐    runStart = wrapSlot(qf, runStart + 1);
➑  } while (qf.slots[runStart].isCont);
  }

➒return runStart;
};

First ➊ we have a findClusterStart that just looks for the start of the cluster that includes a given slot; it just goes backward until it reaches a slot with the isShifted bit unset. Now we can study locateRun. After determining the cluster start ➋ it moves forward ➎ until reaching the target quotient slot. Every time it encounters an occupied slot ➌ it increments runNumber; on exiting the loop ➍ this variable tells us the ordinal number of the quotient's run within the cluster. (This is not the actual slot yet; it is only the count of occupied runs encountered before the target quotient.)

Now ➏ the function starts from the cluster start and advances through runs. The crucial things to remember are that a run may contain multiple occupied slots, and continuation slots have isCont set, so the code skips those slots ➐ until it reaches the first one of the next real run ➑. At the end ➒ runStart is the first slot of the run associated with quot as we wished.

Bye for now! In the next article in the series, we will study how to maintain Quotient Filters, by adding and removing values.

Questions

11½–5. Why not make it simpler? We could have written the return in the createQuotientFilter function as follows; why would it have been a bad idea?

  return {
    p,
    q,
    r,
    s,
    c,
    slots: Array(s).fill({
      rem: 0,
      isOcc: false,
      isCont: false,
      isShifted: false
    })
  };

11½–6. Unneeded test? We know that the QF will never be full, so why do we need the test for slot !== runStart at ➐ in the find code?

Want to get the book?

Part 6: Quotient Filters - the Theory

Federico Kereki — Wed, 14 Oct 2026 18:30:33 +0000

In the previous articles of this series (from here onwards) we saw Bloom Filters, with restrictions on removing added values. Here we'll see Quotient Filters, which free the caller from those limits.

Quotient Filters

Bloom Filters answer one question cheaply: "Have I possibly seen this value before?" An SBF cannot support removals, and a CBF can, albeit at a cost: it requires more memory, and to ensure a removal causes no problems, the caller must do extra work. Quotient Filters (QF) work differently to avoid these issues.

A QF computes a single hash per item and splits it into two parts: a quotient that determines a slot in an array, and a remainder, which is stored in that slot as a small fingerprint. Because both the quotient and remainder come from a single source rather than several unrelated ones, the structure preserves enough information to support removals, using about the same memory as a comparable Bloom Filter.

Since the structure may be intimidating, let's start with an example of a built QF and how to search it, and we'll leave additions and removals for upcoming articles.

The Structure of Quotient Filters

A QF is, in some aspects, similar to a Hash Table with Open Addressing (see Chapter 11 for more on that) but there are some differences. In essence:

Depending on how many values (n) you want to store, a size (s) is determined. Traditionally, the size is always a power of 2 so you can use bitwise operations for speed. A QF consists of s slots, each including content and three additional metadata bits. The table is used in circular fashion, so after the last element you loop back to the table's first.
For each value to store, we compute a p-bit "fingerprint" hash, then split it into a q-bit quotient (such that 2^q = s) and an r-bit remainder; we have p = q + r. We will use the quotient as an index to determine the canonical/home slot where we would want to store the remainder. As with hash tables, the slot may already be in use, so we may need to move elements around.

In a QF, all remainders corresponding to the same quotient will be stored contiguously, in ascending order, in one run. If we have two or more runs such that each one immediately follows the previous one, we call that sequence a cluster. Runs within a cluster appear in increasing order of their quotients.

You may be wondering how the structure works if we store only remainders. A good question, but we'll also have three metadata bits for each slot, and they will allow us to link each remainder (rem) to the corresponding quotient:

isOcc[j] ("is occupied") is true if there is at least one value (stored somewhere in the table that corresponds to the quotient j.
isCont[j] ("is continuation") is true if the element physically in slot j is not the first element of its run.
isShifted[j] is true if the element at slot j is not in its own canonical slot; it had to be displaced.
A totally empty, unused slot has its three metadata bits unset.

We've had several definitions; let's look at an actual QF and study how remainders and metadata bits work. Don't worry now about how the table was created; we'll get to that later.

An Example of Quotient Filters

A sample QF would look like the one shown in Figure 11½–11.

Figure 11½–11: A QF, with 4 runs in 12 slots. Slot for q=15 starts at the right and wraps around.

The size of a QF is usually a power of 2; here we have 16 slots, corresponding to q=4 bits. We are not showing actual remainders, but assume they require r=5 bits so we can show letters (A=1, B=2, C=3, etc.) to simplify. In our case, then p=9.

After creating the empty QF, we added values E, G, K, and L for quotient 4; B and D for quotient 5; C, F, and W for quotient 7; and U, Y, and Z for quotient 15. In practice, the same remainder will often occur for different quotients, but to make the example clearer, we assume all remainders are distinct.
The top row, slot #, just numbers the slots from 0 to 15. Remember that the table is circular, so slot 0 follows slot 15.
The second row, isOcc, shows for which quotients there is at least one value. Positions 4, 5, 7, and 15 are set, and all the rest are not.
The third row, isCont, is set when the element corresponds to the same run as the immediately previous one.
The last row, isShifted, shows whether the value is in its home slot.

Let's figure out the runs, and that will make everything clearer.

For quotient 4, isCont and isShifted are both 0, so the run starts at slot 4. Slots 5 through 7 have isCont set, so those three values are in the same run. The next slot (8) has isCont not set, so that's a different run. We conclude that the run for quotient 4 includes E, G, K, and L.
For quotient 15, it's the same case. The only thing to keep in mind is that the table is circular, so the U at slot 15 is followed by Y and Z at slots 0 and 1.
For quotient 5, isShifted is set, so the value there corresponds to a different quotient, not 5. To find the start of the run we want, we must first go back until we find a value with isShifted unset, which appears at slot 4. Then we move right along both the isOcc and isShifted rows, finding that the run for quotient 4 starts at slot 4, and the run for quotient 5 starts at slot 8. Now, moving right to slot 10, where isCont is not set, we deduce that the run for quotient 5 includes B and D.
For quotient 7, the case is similar. Go left to the start of the run for quotient 4, then move right past the start of the run for quotient 5 at slot 8, and find the run for quotient 7 from slots 10 to 12, including C, F, and W.

Operations with a Quotient Filter

Now we can sketch how basic operations work; we'll see actual code in the following articles in this series. For starters, how do we search for a value? The logic is as follows:

Use the hash function to determine the quotient and remainder for the value;
Locate the run for that quotient; if there's no run, the value isn't in the QF.
Start scanning the run for the remainder; if you find the value, the search was successful, but if you go past the end of the run or reach a value higher than your remainder, the search is unsuccessful.

To add a new value, the logic would run along the lines of:

Use the hash function to determine the quotient and remainder for the value;
If there is no run for that quotient and the corresponding slot is empty, just store the remainder there and set the metadata bits accordingly.
If there's a run for that quotient, you'll have to locate it, determine where the new value should go, and "bump" the following values forward. This may force changing metadata for values in other runs.
If there's no run for that quotient, you'll have to find the end of the previous run, move other values forward, and fix metadata bits.

Finally, removing a value requires:

Find the corresponding run for the quotient and the slot for the remainder;
Remove the value and move the following values to the left, fixing metadata bits if needed.

These are just sketches; in the next article we'll cover creating and searching a QF, and then we'll look at the (longer, more complex) code for adding and removing values.

Bye for now! In the next article in the series, we will study how to size, create, and search Quotient Filters.

Want to get the book?

Part 5: Counting Bloom Filters

Federico Kereki — Mon, 12 Oct 2026 16:17:08 +0000

In previous articles in this series, we saw Bloom Filter implementations that didn't allow removing values without later producing wrong answers. Here we'll see Counting Bloom Filters, which (with an important restriction) allow both adding and removing values.

Counting Bloom Filters

In the previous parts, we considered Standard Bloom Filters and Double Hashing Bloom Filters. We saw how to create, update, and search them, but eventually realized we couldn't remove values from the filter without causing "collateral damage" and making the filter produce wrong answers. In this part we'll show a variant, a Counting Bloom Filter, that (with an important restriction) allows both adding and removing values.

When we tried to remove a value from a Standard Bloom Filter, we found that we could reset a bit set by other additions. The solution we can consider - and let's just consider additions and searches for now - is:

Instead of an array of booleans, we will work with an array of counters.
When we add a value to the filter, we will increment the corresponding counters by one, as determined by the hash functions.
When we search for a value, instead of checking for true bits, we check whether all the counters are nonzero.

Let's see how we'd implement this.

Sizing a Counting Bloom Filter

When sizing a CBF, there's an extra factor to consider. Since the CBF just differs from a BF because it has a count map instead of a bit map, determining the size of the bit map and the number of hash functions to use require exactly the same calculations; nothing new here. However, there's an extra detail: how large should the counts be, what's the maximum value we should expect?

To save memory, we want to use the smallest possible counters, in bits. However, we can't guarantee that, in some cases, the added values won't cause a counter to overflow. We will pick a size that keeps the overflow probability acceptably low, so we can basically ignore the issue.

The basic approach would start by observing that the average number of "hits" for a given slot is hn/b, where h, n, and b are as before: number of hashes, number of values to store, and size of the count map. To consider instead the maximum count gets into probabilistic arguments involving Poisson distributions, which we won't get into, but there are published results that show that for the sizing formulae we are using, 4-bit counters (counts 0 to 15) have a probability of overflow on the order of 10^(‑15); essentially ignorable. If you may have insertions with heavy duplication (same item inserted again and again) then 5‑6 bits (counts up to 31 or 63) are usually overkill.

Even so! How would you deal with a possible overflow? We'll leave that topic to question 11½–4, because the change isn't hard, and we'll focus on simpler logic.

Creating and Adding to a Counting Bloom Filter

We can start with the BF code. We just have to change how we create the filter and how we use it.

const newCountingBloomFilter = (n, eps = EPSILON) => {
  const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
  const h = Math.max(1, Math.round((b / n) * LN2));

  return {
    b,
    h,
➊  count: new Array(b).fill(0)
  };
};

const add = (filter, value) => {
  for (const idx of getIndices(filter, value)) {
➋  filter.count[idx]++;
  }
};

const find = (filter, value) =>
➌ getIndices(filter, value).every((idx) => filter.count[idx] > 0);

There are only three changes with regard to what we saw earlier. When we initialize the array ➊ we fill it with zeroes instead of false. On adding a value ➋ we increment the counter instead of setting it to true. Finally, when searching ➌ non-zero counts are equivalent to a set bit.

Going back to our BF example, Figure 11½–7 below shows how the counts would look after adding three of the Marx brothers.

Figure 11½–7: Three additions to a CBF, using a count map instead of a bit map

If you compare this with Figure 11½–2, the involved hash-calculated positions are the same, but now when two or more values hash to the same place, we increment the count instead of setting a bit.

Removing a value from a Counting Bloom Filter

Now we could implement a remove operation as follows - but there's a hidden potential issue!

const remove = (filter, value) => {
➊if (find(filter, value)) {
➋  for (const idx of getIndices(filter, value)) {
      filter.count[idx]--;
    }
  }
};

The logic seems straightforward. We first check ➊ if the value is in the filter, and if so ➋ we decrement all its counters; what could go wrong? Remember that find may produce false positives; even if it returns true, the value may not have been added to the filter, and you would decrement counts for other values, even producing false negatives; bad!

For instance, we earlier saw that GUMMO produced a false positive. If we use the logic above, the resulting situation would be as shown in Figure 11½–8 below.

">
Figure 11½–8: Removing GUMMO, a false positive, generates a problem.

But what happens now if we search for CHICO, which we added to the filter? Figure 11½–9 shows that this produces a false negative; a no-no!

Figure 11½–9: After removing GUMMO we get a false negative for CHICO.

The issue is clear: as with a BF, we shouldn't remove a value unless we're sure it was added to the filter, and we can't rely on a find operation because it may produce false positives, as in the case we just showed.

This means we can use a CBF for removals only if we have a secondary way to ensure the value to be removed was actually inserted. This, of course, means the caller is responsible for keeping the structure healthy, and that's either a risk (if done wrongly) or a costly chore (if done rightly). Figure 11½–10 shows a possible flowchart.

Figure 11½–10: Using a secondary store for checks allows successful removals

With this approach, counts guarantee you never produce false negatives: adding a value increments some counts, removing that value decrements the same counts, and no other counts are affected.

A CBF is thus a first approximation to a Bloom Filter that allows removals, with high performance but a separate risk, or the need for a secondary test. We will move on to other implementations that may be costlier or more complicated but place fewer restrictions on users. Next, we'll consider the first option: Quotient Filters.

Bye for now! In the next article in the series, we will study Quotient Filters, which allow removals with fewer issues.

Questions

11½–4. Over the top? The usual solution to counter overflows is to check the count before adding a value; if it's already at the maximum, don't modify it. When removing a value, do a similar test, and if the count is at maximum, do not decrement it. (See the changed logic below.) What are the consequences of this logic in terms of false positives and false negatives?

const MAX_VALUE = 15; // 4-bit counters assumed

const add = (filter, value) => {
  for (const idx of getIndices(filter, value)) {
    if (filter.count[idx] < MAX_VALUE) {
      filter.count[idx]++;
    }
  }
};

const remove = (filter, value) => {
  if (find(filter, value)) {
    for (const idx of getIndices(filter, value)) {
      if (filter.count[idx] !== MAX_VALUE) {
        filter.count[idx]--;
      }
    }
  }
};

Want to get the book?

Part 4: Double Hashing Bloom Filters

Federico Kereki — Sat, 10 Oct 2026 17:29:26 +0000

In the previous article in this series, we implemented Bloom Filters, and now we'll see a better-performing version, Double Hashing Bloom Filters.

Double Hashing Bloom Filters

In the BF implementation we saw, we calculated the required bit positions by repeatedly calling a full SHA-256 hash function, changing only the seed each time. The code we used was as follows.

const getIndices = (filter, value) =>
  Array.from({ length: filter.h }, (_, i) =>
    hashWithSeed(String(value), i, filter.size)
  );

This works well, but it's a bit wasteful. Every call to hashWithSeed rehashes the entire value from scratch, and SHA-256, being a cryptographic hash, is deliberately expensive to compute because it's meant as a security feature. For a large Bloom filter, this may become a bottleneck.

However, one insight avoids the need for so many distinct, independent hashes. We can borrow a technique from hash tables, double hashing (see the "Double Hashing" section in Chapter 11 of the book) and get all the needed bit positions from just two hash calculations. The Kirsch-Mitzenmacher technique, named after the authors of a 2006 paper that developed the method, does that.

Creating a Double Hashing Bloom Filter

The core idea for our Double Hashing Bloom Filter (DHBF) is to compute two independent hashes, h1 and h2, and derive the h needed values as in double hashing:

index_i = (h1 + i * h2) mod m, for i = 0, 1, …, h-1

As with searching, we start at bit h1 and then advance (cyclically) in h2-sized steps; h2 must be non-zero. The new getIndices function is now as follows - but we'll have to consider that not all h2 values work!

const getIndices = (filter, value) => { 
  const h1 = hashWithSeed(String(value), 0); 
➊const h2 = hashWithSeed(String(value), 1) || 1;    
  return Array.from( { length: filter.h }, 
     (_, i) => (h1 + i * h2) % filter.b ); 
};

The code is exactly as we saw before; the only difference ➊ is that we make sure h2 is not zero. Should hashWithSeed return 0, 1 would be used instead.

If you remember what we saw when we first studied double hashing (see the "Adding a Value to a Table That Uses Double Hashing" section in Chapter 11) a bad choice of h2 may cause loops, which we have to prevent. In terms of our logic here, h2 and the size of the table (filter.b) must have no common factors. The simplest solution is to ensure the table length is prime, which leads to the following code.

const newDoubleHashingBloomFilter = (n, eps = EPSILON) => {
  const ln2 = Math.log(2);
➊const b = findNextPrime(Math.ceil(-(n * Math.log(eps)) / (ln2 * ln2)));
  const h = Math.max(1, Math.round((b / n) * ln2));

  return {
    b,
    h,
    bits: new Array(b).fill(false)
  };
};

The code is the same as before, but we now force b to be prime ➊ as we did in the "Creating a Table That Uses Double Hashing with Prime Lengths" section in the previous chapter of the book. (Another possibility exists; see question 11½–3.)

Adding a value to a Double Hashing Bloom Filter

The logic for adding a value to a DHBF is the same as for SBF, because it depends on whatever getIndices returns. Let's just repeat the code we saw previously.

const add = (filter, value) => {
  for (const idx of getIndices(filter, value)) {
    filter.bits[idx] = true;
  }
};

For the Marx brothers example, we earlier had a bit array with 10 elements. Since 10 is not prime, we'd use 11 bits instead. For clarity, let's assume the hash functions return the same values as before, though they are called with different parameters.

We'd calculate just two hashes for GROUCHO, 2 and 7, so the bits to set would be 2, 9 (2+7), and 5 (9+7 mod 11).
For HARPO, the first two hashes are 6 and 5, so we would set bits 6, 0 (6+5 mod 11), and 5 (0+5).
Finally, for CHICO, the hashes are 1 and 9, so we set bits 1, 10 (1+9), and 8 (10+9 mod 11).

With a DHBF, we'd end with bits set at positions 0, 1, 2, 5, 6, 8, 9, and 10.

Searching for a value in a Bloom Filter

Given that we have delegated calculating the bit positions to use to the getIndices function, the same code we used for SBF works here.

const find = (filter, value) =>
  getIndices(filter, value).every((idx) => filter.bits[idx] === 1);

To rework the examples from the previous section:

Searching for CHICO would check bits 1, 10, and 8, just as we saw above, and finding all set to 1 would return a "maybe".
Searching for ZEPPO would check bits 3, 10, and 6 (can you work out why?) so it would return a "no"; bit 3 is not set.
Searching for GUMMO would check bits 1, 3, and 5; in this case, the search would return a "no" instead.

One additional point to highlight: With an SBF, there's a clear possibility that some of the hashes will be repeated. Repeated bit positions help produce more false negatives: if you check fewer bits, your probability of finding a zero is lower. With a DHBF, the way we generate the indices of the bits to test ensures we will always have a set of distinct positions, making the structure work better.

Bye for now! In the next article in the series, we will see Counting Bloom Filters, which allow removals under some conditions.

Questions

11½–3. A powerful solution. Show that if you force the length of the bit table to be a power of 2 and h2 to be odd, there will be no loops. Is this a practical solution? Why or why not? Show the code to implement this.

Want to get the book?

Part 3: Bloom Filters - the Practice

Federico Kereki — Fri, 09 Oct 2026 11:25:37 +0000

In the previous article in this series, we covered the theory of sizing and using Bloom Filters; now let's actually implement them with full JavaScript code.

Creating a Bloom Filter

A BF will be implemented as an object with three properties: b and h as described above, and bits, an array with b bit flags, all initially set to 0. (It could be argued that a BF user need not know its internals; see question 11½‑1.) We could skip including b since it's just the length of the bits array, but let's not worry about that now.

const EPSILON = 0.01;
➊ const LN2 = Math.log(2);
➋ const LN2_SQ = LN2 * LN2;

const newStandardBloomFilter = (n, eps
![ ](https://dev-to-uploads.s3.us-east-2.amazonaws.com/uploads/articles/655r2sekwgs7q1x4ppd8.png)

 = EPSILON) => {
➌ const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
➍ const h = Math.max(1, Math.round((b / n) * LN2));

  return {
    b,
    h,
    bits: new Array(b).fill(0)
  };
};

Just as a minimal optimization, we define two constants ➊ ➋ to avoid redoing calculations if we create more than one filter. Then ➌ ➍ we use those values to directly implement the results we found. We can now create a BF; now let's see how to update it. (See question 11½‑2 for an optimization as to memory usage.)

Adding a value to a Bloom Filter

How do we add a value to a BF? We'll need a function to produce a hash value from a string. The result should be between 0 and b-1. Using that function, we will write a getIndices function that will return the h positions that correspond to the string.

const crypto = require("crypto");

const hashWithSeed = (value, seed, limit) =>
  crypto
➊  .https://dev.to/fkereki/part-4-double-hashing-bloom-filters-31l5createHash("sha256")
➋  .update(`${seed}:${value}`)
    .digest()
➌  .readUInt32BE(0) % limit;

const getIndices = (filter, value) =>
➍ Array.from({ length: filter.h }, (_, i) =>
     hashWithSeed(String(value), i, filter.size)
   );

The hash generation uses SHA-256 ➊ to produce a stable, cryptographic fingerprint for each value and seed pair. It combines the seed and the item ➋ as a string like "2:GROUCHO", hashes that, and then takes the first 32 bits of the digest and reduces it modulo the Bloom filter's bit-array size ➌. This gives a deterministic index to the bit array, which is exactly what we need. Finally ➍ getIndices generates an array of size h with all the calculated hashes; each hash is different because we combined the value with distinct seeds.

Given these functions, adding a value is quite short.

const add = (filter, value) => {
  for (const idx of getIndices(filter, value)) {
    filter.bits[idx] = 1;
  }
};

The getIndices function returns an array of the bit positions we need to set, and we do that one by one. We're done! Now, let's do searches.

Searching for a value in a Bloom Filter

With all the code we showed, search can be done in a very concise way, a "one liner" in fact.

const find = (filter, value) =>
  getIndices(filter, value).every((idx) => filter.bits[idx] === 1);

As when adding a value, the getIndices function returns an array with the positions of the bits we have to check, and we use .every to verify that all those bits are 1.

Deleting a value from a Bloom Filter

If adding a value to a BF just requires setting some bits to 1, you might think that removing a value would imply zeroing those same bits - but that won't work! In fact, you cannot remove a value from a BF without possibly making it produce wrong answers, as we'll see.

Let's go back to the example with the Marx brothers. Suppose you wanted to remove GROUCHO and then set bits 2, 7, and 4 to zero. Figure 11½–5 below shows the result.

Figure 11½–5: Removing a value may unset bits that were also set by other previous values

Now, there's a problem. What happens when you search for HARPO? You would check bits 6, 5, and 2 - and find that bit 2 is now 0! Since all the bits corresponding to an item must be set to 1 for it to be considered present, you'd conclude that HARPO was never added to the Bloom filter; see Figure 11½–6.

Figure 11½–6: After removing GROUCHO, a search for HARPO produces a false negative

We'll consider Bloom filters that allow deletions, but first we'll study a variant: a Double Hashing Bloom Filter, which uses a technique that provides better overall performance.

Bye for now! In the next article in the series, we'll look at the better-performing Double Hashing Bloom Filters.

Questions

11½‑1. Do it with class! In the book, we have always been working in a functional way and used few classes. Can you rewrite the Bloom Filter code to use a class instead? Alternatively, you may want to use closures. The goal here is to hide as many internal details as possible.

11½‑2. Getting down to bits. Using an array of numbers wastes a lot of memory, because you just need 1 bit at each position. Rewrite the code using the Unit8Array type and bitwise operators to minimize memory usage. Each byte in the array should provide 8 bits.