Saurabh

Posted on Oct 19

Bloom Filters Explained: A Simple Guide With Real-World Examples and JavaScript

#javascript #algorithms #tutorial #beginners

Have you ever wondered how a system can check whether something might exist among millions of records without storing every single record in its memory?

Imagine you are building an application with 10 million registered users.

Whenever somebody enters an email address, your application needs to check whether that email has already been registered.

The straightforward solution is to query your database. But imagine that your application performs millions of such checks every day. Could you avoid some unnecessary database queries?

One interesting solution is a Bloom Filter.

The name might sound complicated, but the basic idea is surprisingly simple. Let's understand it from scratch, explore where it is useful, and build a small working implementation in JavaScript.

1. First, understand the problem

Suppose you maintain a website with the following registered users:

alice@example.com
bob@example.com
charlie@example.com
david@example.com

When a new visitor enters alice@example.com, your application needs to determine whether the email already exists.

You could store all registered emails in a database or an in-memory data structure such as a Set.

That works well. In many applications, an ordinary database or Set is exactly what you should use.

But what happens when your data grows significantly and checking every possible record becomes expensive?

For example, finding that a particular item does not exist in a large database may still require accessing storage or checking an index.

What if we had a much smaller structure whose main job was to quickly tell us when an item definitely does not exist?

That is the problem a Bloom Filter helps solve.

2. What exactly is a Bloom Filter?

A Bloom Filter is a space-efficient data structure that answers a simple question:

Have I probably seen this item before?

It does not store the original items like a normal Set. Instead, it maintains a collection of bits and uses hash functions to mark positions associated with each item.

Its answers have two possible meanings:

Definitely not present: The item was not added to this filter.
Possibly present: The item may have been added, but we cannot be certain.

Notice the word possibly. It is important.

A Bloom Filter can occasionally say that an item might exist even when it was never added. This is called a false positive.

The standard Bloom Filter is designed to avoid false negatives, provided items are inserted and checked correctly using the same filter.

Let's see why.

3. Imagine a board full of tiny lights

Forget the code for a moment.

Imagine a board with 10 small lights. Initially, every light is switched off.

We represent an off light with 0 and an on light with 1.

Our empty board looks like this:

0 0 0 0 0 0 0 0 0 0

Now imagine every email address is associated with three positions on this board.

For example, when we add Alice's email, our hash functions point to positions 1, 4, and 7.

We switch those positions on.

0 1 0 0 1 0 0 1 0 0

That's it. The board now contains information about Alice, but it does not contain her email address.

Next, we add Bob's email. Suppose it maps to positions 2, 4, and 8.

After adding Bob, the board becomes:

0 1 1 0 1 0 0 1 1 0

Notice something interesting: position 4 was already on. Adding Bob did not require any additional information to be stored there.

Now let's check another email address, Eve.

Suppose Eve maps to positions 1, 4, and 8. All three positions are already on.

Our Bloom Filter says that Eve's email might exist.

But we never added Eve!

Alice and Bob happened to switch on all the positions associated with Eve. Our tiny board cannot tell which items originally switched on each light.

This is the key idea behind a Bloom Filter: it remembers which positions have been marked, not the original items that marked them.

In a real implementation, the positions are calculated using hash functions rather than chosen manually.

4. What are hash functions, and why do we need them?

A hash function takes an input and turns it into a number.

For example, a hash function might turn alice@example.com into 471. A different hash function might turn the same email into 1204, and a third into 987.

But our board only has 10 lights, numbered 0 to 9, so we need a valid position. The fix is to take the remainder after dividing by the board size (the % operator):

471 % 10 = 1
1204 % 10 = 4
987 % 10 = 7

That's how Alice ended up at positions 1, 4 and 7 in the previous section.

When adding an item:

Pass the item through each hash function.
Use % size to turn each result into a position in the bit array.
Change those bits from 0 to 1.

When checking an item:

Pass the item through the same hash functions.
Calculate the same positions.
Check whether every one of those bits is on.

If even one bit is off, the item definitely was not added. If every bit is on, the item might have been added, or other items might have switched those bits on.

One rule matters a lot: hash functions must be deterministic. The same input must always give the same positions. If "alice" hashed to 1, 4, 7 when added but to 2, 5, 9 when checked, you would look at the wrong lights and wrongly say "not present". The filter would then have false negatives, which a Bloom filter must never have.

A good hash function also spreads its results evenly across the board. If it favors certain positions, those lights fill up quickly and false positives become more common.

5. What is a false positive?

Let's revisit our example.

Alice and Bob switched on several lights. Later, Eve's email mapped to positions that were already switched on.

The filter returned a positive result even though Eve was never added.

This is a false positive.

It is not a programming bug. It is an expected trade-off of a standard Bloom Filter.

The important thing is that the probability can be controlled.

Several factors affect the likelihood of a false positive:

Size of the filter: More bits generally provide more space to represent the same number of items.
Number of items: Adding more items makes more bits switch on, increasing the chance of overlap.
Number of hash functions (k): Too few, and different items overlap easily. Too many, and each item switches on so many lights that the board fills up quickly. There is a sweet spot in between.

If a filter becomes too full, false positives become more likely. That is why choosing an appropriate capacity and target false-positive rate matters.

For example, a target false-positive rate of 1% means that approximately 1% of queries for items that were not added may return a positive result under the design's expected operating conditions. It does not mean that 1% of all positive answers are necessarily wrong.

That distinction matters when interpreting results.

How big should the filter be?

You don't have to guess. If you know how many items you expect (n) and the false-positive rate you can tolerate (p), two formulas give the best size and number of hash functions:

Bits needed: m = -(n × ln p) / (ln 2)²
Hash functions: k = (m / n) × ln 2

Here are some common targets:

Target false-positive rate	Bits per item	Hash functions
10%	about 4.8	3
1%	about 9.6	7
0.1%	about 14.4	10

So a rough rule is about 10 bits per item and 7 hash functions for a 1% false-positive rate. For 1 million emails, that works out to roughly 9.6 million bits, which is about 1.2 MB. A Set holding a million email strings would need far more.

The same calculation in code:

function optimalSize(n, p) {
  const m = Math.ceil(-(n * Math.log(p)) / Math.log(2) ** 2);
  const k = Math.max(1, Math.round((m / n) * Math.log(2)));
  return { m, k };
}

console.log(optimalSize(1_000_000, 0.01));
// { m: 9585059, k: 7 }

const { m, k } = optimalSize(1_000_000, 0.01);
const filter = new BloomFilter(m, k); // the class we build in the next section

This is why the BloomFilter(1000, 3) we use below is only a toy. Real filters should be sized for the data they will hold.

6. Let's build a Bloom Filter in JavaScript

Theory is useful, but let's put it into practice.

We'll create a small educational implementation using JavaScript. It will accept items, mark positions in a bit array, and tell us whether an item might be present.

The example uses a basic, non-cryptographic hash function to keep the implementation understandable. It is for learning purposes, not a production-ready implementation.

Step 1: Create a hash function

function hashString(value, seed) {
  let hash = seed >>> 0;

  for (let i = 0; i < value.length; i++) {
    hash ^= value.charCodeAt(i);
    hash = Math.imul(hash, 16777619);
  }

  return hash >>> 0;
}

This function converts a string into a 32-bit unsigned integer.

We use two different seeds to derive multiple positions for each item. The code uses a technique called double hashing, which generates several positions from two hash values.

You do not need to memorize the hashing details to understand how the Bloom Filter works. The important part is that the same input consistently produces the same positions.

Step 2: Implement the Bloom Filter

class BloomFilter {
  constructor(size = 1000, hashCount = 3) {
    this.size = size;
    this.hashCount = hashCount;

    // Eight bits are stored in each byte.
    this.bytes = new Uint8Array(Math.ceil(size / 8));
  }

  getIndexes(value) {
    const firstHash = hashString(value, 2166136261);

    const secondHash =
      (hashString(value, 0x9e3779b9) | 1) >>> 0;

    return Array.from(
      { length: this.hashCount },
      (_, i) => (firstHash + i * secondHash) % this.size
    );
  }

  setBit(index) {
    const byteIndex = Math.floor(index / 8);
    const bitPosition = index % 8;

    this.bytes[byteIndex] |= 1 << bitPosition;
  }

  isBitSet(index) {
    const byteIndex = Math.floor(index / 8);
    const bitPosition = index % 8;

    return (
      (this.bytes[byteIndex] & (1 << bitPosition)) !== 0
    );
  }

  add(value) {
    for (const index of this.getIndexes(value)) {
      this.setBit(index);
    }
  }

  mightContain(value) {
    return this.getIndexes(value).every(
      (index) => this.isBitSet(index)
    );
  }
}

Let's break down the important parts.

constructor()

Creates a filter with 1,000 available bit positions by default and uses three hash-derived positions per item.

We use a Uint8Array to store eight bits per byte. This allows the example to use an actual packed bit array rather than reserving an entire byte for every position.

getIndexes()

Calculates the positions associated with an item. The same item produces the same positions as long as the filter parameters and hash implementation remain unchanged.

add()

Marks every calculated position as 1.

mightContain()

Checks every position. If any required bit is 0, it returns false. Otherwise, it returns true, meaning the item might exist.

The method is deliberately called mightContain() rather than contains(). A Bloom Filter cannot guarantee that a positive result is correct.

Step 3: Try it out

Let's add a registered email address and check a few values.

const filter = new BloomFilter(1000, 3);

filter.add("alice@example.com");

console.log(
  filter.mightContain("alice@example.com")
);

console.log(
  filter.mightContain("bob@example.com")
);

Expected output:

true
false

The filter returns true for Alice because we added her email.

It returns false for Bob because at least one of Bob's required positions is still off.

With this filter's size and current contents, Bob's check returns false. However, another absent email could return true if all its positions happened to be switched on.

That is the false-positive trade-off in action.

Step 4: See a false positive happen

So far we've only seen the filter behave well. Let's break it on purpose by giving it far too little space: 20 emails squeezed into just 64 bits.

const tiny = new BloomFilter(64, 3);

// Add 20 registered users
for (let i = 1; i <= 20; i++) {
  tiny.add(`user${i}@example.com`);
}

// Added items are always found
console.log(tiny.mightContain("user7@example.com")); // true

// Now check 200 emails we never added
const falsePositives = [];
for (let i = 21; i <= 220; i++) {
  const email = `user${i}@example.com`;
  if (tiny.mightContain(email)) falsePositives.push(email);
}

console.log(`False positives: ${falsePositives.length} out of 200`);
console.log(falsePositives.slice(0, 3));

Output:

true
False positives: 60 out of 200
[ 'user25@example.com', 'user26@example.com', 'user30@example.com' ]

Look at what happened:

user7@example.com was found, as it always will be. There are no false negatives.
60 of the 200 emails we never added were reported as "might exist". With 37 of the 64 bits switched on, a random absent email has a good chance of landing entirely on lights that other users already switched on.
By the sizing rule from section 5, 20 items at a 1% target need about 192 bits. We gave the filter 64, so it is overcrowded and the false-positive rate is high.

Try changing 64 to 200 and run it again. The false positives should drop sharply. That is the memory-versus-accuracy trade-off in action.

One important limitation: This is a teaching implementation, not a recommendation to write your own production hashing algorithm. Real systems should use a tested Bloom Filter library with appropriate sizing, hash behavior, concurrency handling, and operational monitoring.

7. A real-world example: Checking whether a username exists

Imagine you're building a registration service that handles millions of username availability checks.

A simplified request flow might look like this:

User enters a username
          |
          v
   Check Bloom Filter
          |
     +----+----+
     |         |
   Absent    Possibly
     |         |
     v         v
 Continue    Check database
 registration   |
                v
        Is username registered?

Let's consider both cases.

Case A: The Bloom Filter says the username is definitely absent.

The application can skip a preliminary database lookup whose only purpose was to check whether that username existed.

It can continue with the normal registration process.

The database must still enforce a unique constraint on the username. Otherwise, two users could try registering the same username at the same time.

Case B: The Bloom Filter says the username might exist.

The application queries the database to confirm the result.

If the username exists, it can tell the user that the name is unavailable.

If the database says the name is free, the application can continue registration. The Bloom Filter may simply have produced a false positive.

This approach can help reduce unnecessary database lookups when many queried usernames are absent.

There is an important engineering detail here: the filter must stay consistent with the actual registered-user data. Adding items too early or failing to update the filter after successful registrations can undermine the reliability of the optimization.

A Bloom Filter is an optimization, not a replacement for database correctness.

8. Where else are Bloom Filters useful?

The username example is only one possible application.

A. Databases and storage engines

Databases sometimes need to check whether a key may be present in a particular on-disk data structure.

Checking storage can be more expensive than checking information already available in memory.

A Bloom Filter can help the database avoid some unnecessary storage reads when it determines that a key is definitely absent.

B. Web crawlers

Imagine a web crawler exploring millions of pages.

Before processing a URL, it needs to determine whether that URL may have already been visited.

A Bloom Filter can provide a compact preliminary check. A positive result might require further verification, depending on the crawler's requirements.

This is useful when memory is limited, but a false positive could cause a page to be skipped incorrectly. That trade-off must be considered.

C. Recommendation and advertising systems

A service might want to avoid repeatedly recommending the same item or displaying the same advertisement.

A Bloom Filter can help identify items that may already have been seen.

However, if showing an item twice is unacceptable, the application needs an exact verification mechanism rather than relying solely on the filter.

D. Large-scale data processing

When processing huge datasets, a system may want to avoid performing an expensive lookup for every item.

A Bloom Filter can serve as a compact preliminary check, reducing unnecessary work when a large proportion of the queried items are absent.

The broader pattern is the same: use a small structure to avoid expensive work whenever it can confidently rule an item out.

9. Bloom Filter vs. Set: Which should you use?

A Bloom Filter is not universally better than a Set. Each solves a different problem.

Feature	JavaScript `Set`	Bloom Filter
Stores original items	Yes	No
Memory usage	Depends on stored items and implementation	Usually much smaller for large collections
Absent-item check	Exact	Exact negative result
Present-item check	Exact	May be a false positive
Delete an item	Supported	Not supported by a standard Bloom Filter
Best suited for	When exact membership matters	When memory savings and fast preliminary checks matter

For a small application storing a few hundred usernames, a Set may be simpler and entirely sufficient.

For a large system where memory usage matters and checking absent items is expensive, a Bloom Filter may be worth considering.

The right choice depends on the requirements, not simply on which data structure sounds more advanced.

10. Important limitations to remember

Bloom Filters are useful, but they are not magic.

They cannot recover the original data. The bit array does not tell you which email addresses, URLs, or IDs were inserted.

False positives are possible. A positive result needs verification whenever correctness depends on exact membership.

Standard Bloom Filters do not support deletion. Setting a bit back to zero could accidentally remove information needed by other items. Variants such as counting Bloom Filters can support deletion with additional complexity and storage.

Sizing matters. If you insert substantially more items than the filter was designed for, its false-positive rate can rise.

They are not a security mechanism. The basic implementation presented here is not designed to protect sensitive data, and a Bloom Filter should not replace appropriate security checks.

Understanding these limitations is just as important as understanding how the data structure works.

11. The takeaway

A Bloom Filter is a great example of a practical engineering trade-off.

Instead of storing every original item, it stores a compact representation of information about those items.

In return for saving memory, it accepts uncertainty when the answer is positive.

Remember these three points:

If a standard Bloom Filter says an item is absent, the item was not added, assuming the filter has been used correctly.
If it says an item might be present, the result is not guaranteed to be correct.
It is most useful when ruling out absent items can save significant memory or expensive work.

The next time you encounter a system that handles millions of records, ask yourself: Do we really need to perform an exact lookup every time, or can we cheaply rule out most absent items first?

That is where a Bloom Filter might be worth exploring.

DEV Community