DEV Community: Federico Kereki

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?

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.

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.

" width="537" height="314">
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]--;
      }
    }
  }
};

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.

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.

In my Data Structures and Algorithms in JavaScript book, I discussed Dictionary implementations for exact searches. I am now starting a new series (Chapter 11 !) on Filters and Probabilistic Searching, which you can find at https://tinyurl.com/3kmcvn8u

Federico Kereki — Thu, 08 Oct 2026 12:38:09 +0000

Part 1: Introducing Filters and Probabilistic Searching - DEV Community

In my Data Structures and Algorithms in JavaScript book, we studied Dictionary implementations for...

dev.to

Bloom Filters - the Theory

Federico Kereki — Thu, 08 Oct 2026 11:46:02 +0000

In the first article in this series, we introduced Filters for Probabilistic Searches, and their operations. Here we'll start with Bloom Filters, the first implementation to consider.

Bloom Filters

The first implementation we'll look at is a Bloom Filter (BF). The name has nothing to do with flowers or how the filter behaves; the "Bloom" part comes from Burton H. Bloom, a computer scientist who introduced the structure in a 1970 paper published in Communications of the ACM, "Space/Time Trade-offs in Hash Coding with Allowable Errors".

Interestingly, the structure was a relatively obscure theoretical curiosity for decades before becoming widely used several decades later, when memory-constrained, large-scale systems needed exactly the space/accuracy trade-off Bloom described.

The core idea is to use a bit array and several independent hash functions to record a "fingerprint" of added items. Basically, how you add an item is:

Let the bit array size be b, and the number of hash functions be h. Each hash function maps its input to one of the b positions.
Apply the hash functions to the input, producing h positions for the array. (Yes, some of the h values may be repeated, but ignore this for the moment.)
Set the bit at each of those positions to 1.

Let's see an example. Say b=10 and h=3, and we want to add three of the Marx brothers, GROUCHO, HARPO, and CHICO, to the filter.

Applying the three hashes to GROUCHO may produce 2, 7, and 4; we set the corresponding bits to 1.
Suppose applying the hashes to HARPO produces 6, 5, and 2; we now have bits 2, 4, 5, 6, and 7 set. Note that bit 2 was already set; it stays that way.
Applying hashes to CHICO produces 1, 9, and 6; we have bits 1, 2, 4, 5, 6, 7, and 9 set.

See the following figure for a summary of the three additions; dotted gray lines show bits set more than once.

Figure 11½–2: Three additions to a Bloom Filter

Now for the interesting part: how do we search for a string? The way to do a search is:

Apply the hash functions to the input you want to find, producing h bit positions.
Check those positions: if any of them (at least one) is not set, the input is definitely NOT in the structure.
If all are set, the input may be in the structure, but it could be a false positive!

Let's see some examples. We want to check ZEPPO, CHICO, and GUMMO. First, when we search for ZEPPO, assume the hash functions produce 3, 7, and 8. Since at least one of those bits is 0, we can assert that ZEPPO was never added and is not present. The figure below shows the search, with dotted gray lines indicating the unset bits found. Practically, you wouldn't continue checking after finding the first unset bit; a single 0 is enough to declare the search failed.

Figure 11½–3: A failed search; one unset bit is enough.

Now let's see some possibly successful searches. When we search for CHICO, the hashes produce 1, 9, and 6, and all those bits are set to 1. Suppose that when we search for GUMMO, suppose the hash functions produce 1, 2, and 4; again, all those bits are set to 1. We cannot definitely say the searches were successful; in one case (CHICO), the bits were set because we added that value, but in the other case (GUMMO), other values set the bits.

Figure 11½–4: Both searches find all bits set, but only one value was actually added.

We now know how to use a filter; we need to decide how to size it before we can write the code for additions and searches.

Sizing a Bloom Filter

As we mentioned in the previous section, to appropriately size a BF, you must know n, how many elements to insert, and the false-positive rate, ε, and you'll decide how many bits to use (b) and how many hash functions are needed (h). By the way, ε is usually set at 0.01, 1%, or much less. The lower the value, the fewer the false positives.

Let's do some math; if you wish, skip ahead! If you insert one element, each of the h functions sets a bit. The probability that any insertion does not hit a particular bit is 1‑1/b, so after n insertions with h hashes each, the probability that the bit is still not set would be (1‑1/b)^hn. For large b, this is approximately e^(‑hn/b). You get a false positive if you search for a value that was never inserted, but all the corresponding h bits happen to be set. This false-positive probability is (1‑e^(‑hn/b))^h, and from this result we'll get the sizes we need.

Let's find how many hashes we need. Fixing b and n, the formula depends only on h, and is optimized when h is (b/n) ln(2). Substituting this value into the false-positive formula and simplifying eventually produces 2^(‑(b ln(2)/n)). Equating this to ε, b should be ‑(n ln(ε))/ln²(2). At this point, we have everything we need to start writing code; let's get to it.

Bye for now! In the next article in the series, we will see how to implement the Bloom Filters we described here, with full JavaScript code for all algorithms.

Filters and Probabilistic Searching

Federico Kereki — Thu, 08 Oct 2026 11:36:32 +0000

In my Data Structures and Algorithms in JavaScript book, we studied Dictionary implementations for exact searches. In this article series, we will explain what probabilistic searches are, when they may be needed, and cover Filters, a way to do these searches, showing several data structures with complete JavaScript code, plus examples and even questions for you to work out. This could have been an addendum to Chapter 11 in the book (new title: "Bags, Sets, Maps, and Filters"?) but I prefer a new number (Chapter 11½!) to not modify existing chapter numbers.

Introducing Filters

A common problem in Computer Science is determining whether a key is in a set or map. However, sometimes you just want to know whether the key is absent (for example, to avoid accessing a database, external service, or web page) and can accept false positives if the search just says, "the key may be in the set." This kind of probabilistic search is a cheap pre-filter in front of a more expensive, authoritative access or check.

For example, you could be building a password checker. You have a database with billions of compromised usernames. Given a specific user, you want to quickly check whether he may be in the set. If you had added all compromised users to a Bloom Filter, you could do a very quick check; if the filter says "Absent", you are 100% sure the account wasn't compromised. On the other hand, if the filter says "May be present", then, and only then, you'd search thefindfind extensive database or call an external service to (far more slowly) do the definitive test. Using the filter can speed up many searches, requiring a slow check only for a few.

Figure 11½ -1: Algorithm for exact searches with filters

A full dictionary for exact answers requires more space, and probabilistic searches reduce that significantly, at the cost of occasionally saying "maybe" when the true answer is "no". When we have a large key set and tight memory or latency requirements, and we can tolerate a low, controllable rate of unnecessary extra work, we can accept these false positives. And remember, negative answers will always be correct and final.

ADT for Filters

A filter's behavior is characterized by a parameter with no analog in Dictionary ADTs: the false-positive rate, usually written ε. This number actually quantifies how often you may get false-positive answers. It's expressed as a probability: ε=0.01 means roughly a 1% chance that a find operation will incorrectly return true. This isn't a bug or an implementation quirk; it's a value you consider when deciding which structure to use and how to size it.

Also, as with other structures such as hash tables (see the Hashing section in chapter 11) you must specify how many values (n) you expect to store. Given n and ε, we can calculate the right size for specific filter implementations. The following table shows the Filter ADT.

Table 11½-1: Operations on Filters

There are several interesting comments here.

In the add operation, we do not worry if a value is repeatedly added to the filter. However, in some implementations this may cause issues later, as we'll see.
The remove operation may not be required or allowed. Some structures cannot support it at all; some can. An important issue here is that removing a value that wasn't in the filter may cause false negatives, which breaks the ADT contract!
More extreme still, some filters trade away both add and remove operations after initial construction in exchange for better space and speed; in these cases, the create operation takes the whole set of values used to build the filter instead of the n parameter.
Finally, we could support an empty? operation (given a filter, determine whether it is empty) and a size operation (given a filter, determine how many values it includes) but I'll leave those implementations up to you.

Comparing Dictionaries and Filters

To summarize, Filters differ from Dictionaries in three important ways:

Compactness - Filter implementations use substantially less space than Dictionary implementations, typically a small constant number of bits per element.
One-sided error - The find operation never produces a false negative. However, it may produce false positives at a rate bounded by ε.
Tunable accuracy - ε is a construction parameter and can be driven down (at the cost of more space) as far as the application needs. Dictionaries are always 100% accurate; filters, by definition, are not.

We've covered all the considerations to keep in mind when planning filters; now let's move on to actual implementations.

Bye for now! In the next article in the series, we will start with Bloom Filters, the first implementation we'll be considering.