Bloom Filters: Skipping Lookups That Can Only Miss

Introduction

A Bloom filter is a fixed-size data structure that records which items have been added to a set and answers one question about any item: definitely not in the set, or possibly in the set. A Bloom filter never reports "not in the set" for an item that was added, but a small percentage of queries about items that were never added come back as "possibly in the set" anyway. Those wrong answers are called false positives, and the rate at which they happen is a number you choose when you size the filter.

What you get in exchange for that inaccuracy is memory. A Bloom filter stores no keys, only bits, so a filter holding a million items occupies the same space whether those items are 8-byte integers or 2-kilobyte URLs. At a 1% false positive rate that space is about 1.14 MB, which we will measure against the 88 MB a JavaScript Set used for the same million keys.

This post builds a working filter in TypeScript, derives the two sizing formulas that tell you how many bits and how many hash functions to use, measures the resulting false positive rates against their targets, and covers the operations a Bloom filter cannot support. It continues a thread from the last two posts: the LRU cache decides what to keep, rate limiting decides what to admit, and a Bloom filter decides what not to look up in the first place.

The Cost of a Lookup That Finds Nothing

A cache miss is expensive but productive: the value gets fetched, stored, and served. The lookup worth attention is the one that finds nothing at all. The cache misses, the query goes to the database, the database scans an index, and the answer comes back empty. Full cost, no value, and nothing to cache afterward.

Several common workloads are dominated by exactly that shape:

• Checking whether a username or a short link is already taken, where almost every candidate is free.
• Asking whether a URL has already been crawled, or an event already processed, across a corpus far larger than memory.
• Reading a key from a storage engine that keeps data in many files on disk, where the key lives in at most one of them and most files must be ruled out.

In each case the expensive work happens before the system learns there was nothing to find. A Bloom filter sits in front of that work and answers "definitely not present" for most absent keys, cheaply and from memory.

How a Bloom Filter Works

A Bloom filter is an array of m bits, all starting at zero, plus k independent hash functions. Each hash function maps any key to one position in the bit array.

Adding an item: hash the key with all k functions and set the bit at each resulting position to 1. Bits are only ever set, never cleared.

Querying an item: hash the key the same way and look at those same k positions. If any of them is 0, the item was definitely never added, because adding it would have set every one of those bits. If all k are 1, the item was probably added, but the bits may also have been set by a combination of other keys.

m = 16 bits, k = 3, every bit starts at 0

add("alpha")  sets bits  2,  7, 11
add("bravo")  sets bits  4,  7, 14      (bit 7 was already set by "alpha")

index  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bit    0  0  1  0  1  0  0  1  0  0  0  1  0  0  1  0

query("alpha")  bits  2,  7, 11  ->  all set     ->  possibly present (correct)
query("echo")   bits  5,  7, 11  ->  bit 5 is 0  ->  definitely absent (certain)
query("delta")  bits  4, 11, 14  ->  all set     ->  possibly present (false positive)

The two answers are not equally strong, and that asymmetry is the entire design. "Definitely absent" is a proof: a zero bit is evidence no one ever added this key. "Possibly present" is a guess that gets weaker as the array fills. A Bloom filter is therefore useful precisely where a negative answer lets you skip work, and useless where you need the positive answer to be trustworthy on its own.

A Bloom Filter in TypeScript

Two design decisions turn the description above into practical code.

The first is the bit array. JavaScript has no bit array type, so a Uint8Array holds the bits and two operations address them: position >>> 3 selects the byte (dividing by 8), and position & 7 selects the bit within that byte.

The second is the hash functions. Writing k independent hash functions is unnecessary work. Kirsch and Mitzenmacher showed that two independent hashes are enough to synthesize as many as you need, using h1 + i * h2 for the i-th position, with no meaningful loss in the false positive rate. One requirement comes with that trick: the second hash must be odd, or a key whose h2 lands on a multiple of the array length would map all k positions onto the same bit.

// src/utils/bloom-filter.ts
function hashPair(key: string): [number, number] {
  let h1 = 0x811c9dc5; // FNV-1a offset basis
  let h2 = 0x1000193;
  for (let i = 0; i < key.length; i++) {
    const c = key.charCodeAt(i);
    h1 = Math.imul(h1 ^ c, 0x01000193);
    h2 = Math.imul(h2 ^ c, 0x85ebca6b);
  }
  // Force h2 odd so the probe stride never collapses onto one bit.
  return [h1 >>> 0, (h2 >>> 0) | 1];
}

export class BloomFilter {
  private readonly bits: Uint8Array;
  private readonly m: number; // total bits
  private readonly k: number; // hashes per key

  constructor(expectedItems: number, falsePositiveRate = 0.01) {
    if (expectedItems < 1) {
      throw new RangeError("expectedItems must be at least 1");
    }
    const bits = Math.ceil(
      -(expectedItems * Math.log(falsePositiveRate)) / Math.LN2 ** 2
    );
    this.m = Math.max(8, bits);
    this.k = Math.max(1, Math.round((this.m / expectedItems) * Math.LN2));
    this.bits = new Uint8Array(Math.ceil(this.m / 8));
  }

  private *positions(key: string): Generator<number> {
    const [h1, h2] = hashPair(key);
    for (let i = 0; i < this.k; i++) {
      yield ((h1 + i * h2) >>> 0) % this.m;
    }
  }

  add(key: string): void {
    for (const position of this.positions(key)) {
      this.bits[position >>> 3] |= 1 << (position & 7);
    }
  }

  mightContain(key: string): boolean {
    for (const position of this.positions(key)) {
      if ((this.bits[position >>> 3] & (1 << (position & 7))) === 0) {
        return false; // a zero bit proves this key was never added
      }
    }
    return true; // every bit set: probably added, possibly a collision
  }

  get sizeInBytes(): number {
    return this.bits.byteLength;
  }
}

The method name matters more than it looks. has implies certainty the structure cannot provide, while mightContain (the name Guava uses) tells the next reader that a true needs verifying and a false does not. Every operation is O(k), which is a small constant, and independent of how many items the filter holds.

Sizing: Bits per Item and the False Positive Rate

Two formulas connect the false positive rate you want to the filter you need. For n expected items and a target rate p:

m = -(n · ln p) / (ln 2)²        bits of storage
k = (m / n) · ln 2               hash functions

The constructor above applies both. The second formula is worth understanding rather than memorizing: too few hashes and distinct keys collide too easily, too many and the array saturates with 1s. The optimum sits where roughly half the bits are set.

The consequence to internalize is in the first formula. Divide both sides by n and the item count cancels: bits per item depends only on the false positive rate, never on how many items you store or how large each item is. Filling the filter and measuring against 200,000 keys that were never added confirms both the sizing and the implementation:

target rate | bits per item | hashes (k) | measured rate | size at 1M items
------------+---------------+------------+---------------+------------------
        10% |           4.8 |          3 |        10.11% |          0.57 MB
         1% |           9.6 |          7 |         1.02% |          1.14 MB
       0.1% |          14.4 |         10 |         0.10% |          1.71 MB

Two things to read out of that table. Each tenfold reduction in the false positive rate costs a flat 4.8 more bits per item, so accuracy gets cheaper the more of it you buy. And the absolute numbers are small: storing a million keys with 1% error takes 1.14 MB, while a JavaScript Set holding the same million 16-character keys measured 88 MB of heap in Node. The filter is roughly seventy times smaller, and unlike the Set it would not grow if those keys were full URLs.

One failure mode has no error message. Add more items than the filter was sized for and the false positive rate climbs quietly past the target, because the array fills with 1s. Size for the maximum you expect, track how many items you have added, and rebuild into a larger filter when you approach the limit.

What a Bloom Filter Cannot Do

The bits-only representation that makes the structure small also removes capabilities you may assume are there.

• No deletion. Clearing a key's k bits would introduce false negatives for every other key that shares any of those bits, which breaks the one guarantee the structure offers. A counting Bloom filter replaces each bit with a small counter to support removal, at roughly four times the memory. A cuckoo filter supports deletion and beats a Bloom filter's space at low false positive rates.
• No enumeration. You cannot ask a filter what is in it. The keys were never stored.
• No resizing. Growing means building a new filter from the original data, so that data has to still exist somewhere.
• No counts. A Bloom filter answers membership only. Frequency estimation is a different structure, the Count-Min Sketch.

Where They Are Used

Storage engines built on log-structured merge trees, including RocksDB, Cassandra, and HBase, attach a Bloom filter to each on-disk table. A point lookup consults the filters first and reads only the files whose filter says the key might be there. Without them, reading a key that does not exist would touch every file at every level, which is the most common read in workloads that check for absence.

Content delivery networks use them to solve a different problem. Akamai reported that roughly three quarters of the objects in a production trace were requested exactly once, so caching an object on first sight fills the cache with content nobody asks for again. Tracking first requests in a Bloom filter and caching only on the second request keeps those one-hit wonders out of the cache and cuts the disk writes that come with them.

The same shape appears in application code: recording which posts a reader has already been shown, which events a pipeline has already processed, or which URLs a crawler has already visited. In each case a "definitely not seen" answer is the one that saves the expensive step.

When to Skip the Bloom Filter

A Bloom filter earns its place when three conditions hold together: the set is large enough that exact membership is costly to keep, the lookups it protects are expensive, and queries for absent items are common. Remove any one of those and something simpler is better.

• Small sets. A few thousand items in a Set is exact, simpler, and small enough that the memory argument never arrives.
• Cheap lookups. If the thing being skipped is an in-memory index, hashing the key k times to avoid it is added work, not saved work.
• Answers that must be right. Authorization, billing, and correctness checks cannot act on "probably". A filter can still front those paths as an optimization, but only where a positive answer is verified against the real source.
• Sets that change. Frequent deletions point to a counting Bloom filter or a cuckoo filter instead.

Conclusion

A Bloom filter trades exactness for a flat, predictable memory budget, and it makes that trade in one direction only: it can claim an item is present when it is not, but never claims an item is absent when it is present. That one-sided error is what makes the structure safe to put in front of expensive work, because acting on "definitely absent" is acting on a proof. Sizing it takes two formulas and one decision about how much error you can tolerate, and the cost of that decision is small and linear: roughly 4.8 bits per item for each factor of ten in accuracy.

Key Takeaways

• A Bloom filter answers set membership with no false negatives and a configurable false positive rate, storing bits instead of keys.
• Adding an item sets k bits; a query that finds any of its k bits at zero has proven the item absent.
• Bits per item depends only on the target false positive rate: about 9.6 bits at 1%, and 4.8 more bits for each tenfold improvement.
• Measured rates track their targets closely, and a million keys fit in 1.14 MB against 88 MB for the equivalent Set.
• Overfilling degrades accuracy silently, so size for the maximum, count what you add, and rebuild before the filter saturates.
• Bloom filters cannot delete, enumerate, resize, or count; those needs point to counting Bloom filters, cuckoo filters, or a Count-Min Sketch.