Part 4: Double Hashing Bloom Filters

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.

Comments

[DEV SUPPORTS]

You need to verify your account.

tr.ee/dev-to