How to Implement a Bloom Filter from Scratch

Let's start with the core idea: a Bloom filter is a space-efficient data structure that answers one question—"Is this item definitely not in the set, or maybe in the set?" It never tells you "definitely yes." The "maybe" is where the trade-off lives.

Intuition: thinking about set membership

Imagine you're checking a very large dictionary for a word. You don't need the word's definition—just a quick "yes or no" on whether it exists. A traditional Set (like a hash table) would store every word exactly, using lots of memory. A Bloom filter uses a clever trick: it uses a bit array (just a long string of 0s and 1s) and a few different hash functions.

When you add a word, the hash functions compute several positions in that bit array and flip those bits to 1. When you check a word, the same hash functions compute positions. If any of those bits are 0, the word is definitely not in the set (because we would have set it to 1 when adding). If all the bits are 1, the word is maybe in the set—it could be a real match, or it could be that other words happened to set those same bits to 1. That's the false positive.

Real-world analogy

Think of a club with a secret handshake. The bouncer knows three specific moves (hash functions). When you join, you perform those three moves, and the bouncer makes a note in their notebook (sets three specific bits). Later, when someone claims to be a member, they perform the same three moves. If they fail any move, they're out—definitely not a member. If they nail all three, the bouncer says "maybe" and lets you in, because it's possible someone else happened to know those exact three moves by coincidence.

The guarantee is one-way: no false negatives. If the filter says "no," you can trust that absolutely. That's because we only ever set bits to 1; we never reset them to 0. So a 0 bit means "this item was never added." The "yes" (the "maybe") is always fuzzy. This asymmetry is what makes Bloom filters useful for filtering out obvious non-members before a costly full lookup (like querying a database or disk).

You might wonder: "Why would I ever use a data structure that isn't 100% correct?" The answer lies in two precious resources: memory and speed. In large-scale systems, you often don't need a perfect answer—you need a good enough answer, delivered instantly without draining your server's RAM.

Intuition: The "Net Mesh" Analogy

Think of a Bloom filter like a fishing net.

• A coarse mesh (high false positive rate): The holes are big. It's very light and easy to carry (low memory), but it lets some fish slip through (false positives).
• A fine mesh (low false positive rate): The holes are tiny. It catches everything, but the net is heavy, expensive, and harder to drag (high memory usage).

You choose the mesh based on your needs. If you're filtering spam emails, you might tolerate a coarse mesh (occasionally letting spam through to be deleted later). If you're filtering security tokens, you need a fine mesh.

The "Gatekeeper" Workflow

The most common pitfall is treating a Bloom filter like a normal set. It is not a replacement; it is a gatekeeper.

If the filter says "Definitely Not", you save a trip to the database. If it says "Maybe", you must check the database to be sure. This architecture is why systems like Cassandra, Redis, and Chrome (to block malicious URLs) rely on them.

At its heart, membership testing answers a simple question: "Is this specific item part of a stored set?" You see this everywhere—checking if a username exists in a database, if a URL is in a blocklist, or if a word is in a dictionary.

How it works (Step-by-Step)

To test if an item exists, we don't look for the item itself. We look for the traces it left behind. Here is the exact process:

1. Hashing: We pass the item through our k hash functions.
2. Indexing: Each hash function gives us a specific position (index) in the bit array.
3. Inspection: We look at the bits at those positions.

def might_contain(item, bit_array, hash_functions):
    for hash_func in hash_functions:
        index = hash_func(item) % len(bit_array)
        # If we find a 0, the item was never added
        if bit_array[index] == 0:
            return False  # Definitely not present
    # If all bits are 1, it might be there
    return True  # Maybe present (could be false positive)

The "One-Sided Error" Property

This logic creates a fundamental asymmetry that defines the Bloom filter:

• No False Negatives: If the filter says False ("definitely not"), you can trust it 100%. A 0 bit means "this specific slot has never been touched." If an item requires that slot to exist, and the slot is empty, the item simply isn't there.
• Possible False Positives: If the filter says True ("maybe"), it might be wrong. Different items can map to the same bit positions, turning a 0 to 1 indirectly. This is the trade-off you configure.

Intuition: The "Sieve" Analogy

Think of a Bloom filter like a sieve or a colander used for pasta.

• The "No" (Holes): Anything that falls through the holes (hits a 0 bit) is definitely gone. It's not in the pot. You can discard it immediately.
• The "Maybe" (Mesh): Anything that sits on the mesh (hits all 1 bits) might be pasta. It could be pasta, or it could be a piece of gravel that just happened to get stuck. You must pick it up and inspect it closely (a database lookup) to be sure.

This "definitely not" guarantee is gold for performance. You avoid expensive lookups for everything that falls through the sieve.

Now we arrive at the engine room: hash functions. A Bloom filter isn't magic; it's math. Specifically, it relies on k independent hash functions to distribute your data across the bit array.

The "Independent Sprinklers" Analogy

Imagine you are watering a long garden bed (the bit array). You have k sprinklers (hash functions).

• Independent Sprinklers: Each sprinkler sprays water at a random, distinct location. This ensures the whole bed gets wet evenly.
• Dependent Sprinklers: If all your sprinklers are connected to the same pipe and just shifted slightly, they will spray the same few spots over and over. This leaves large dry patches (unused bits) and creates soggy clumps (collisions).

The "Single Hash" Pitfall

A common beginner mistake is to think: "I only need one hash function, I'll just add 1, 2, and 3 to the result to get the other indices."

// ❌ WRONG: This creates clumps!
def bad_hash(item, i):
    return hash(item) + i  # Just shifts the same pattern

As you saw in the simulation above, this creates clumping. If the base hash lands on index 2, your three indices are 2, 3, and 4. You are filling up the array in little bands. This dramatically increases false positives because unrelated items are likely to overlap in these predictable bands.

Practical Implementation: Double Hashing

So, how do we get multiple independent hashes without running a heavy cryptographic algorithm five times? We use a trick called Double Hashing.

We compute two base hashes, h1 and h2. Then, we generate the i-th hash function using this formula:

This mathematically approximates independence. h2 acts as a "step size" that changes for every item, spreading the indices out across the array m.

# ✅ CORRECT: Double Hashing
def get_indices(item, k, m, h1, h2):
    indices = []
    for i in range(k):
        # Linear combination of two base hashes
        idx = (h1(item) + i * h2(item)) % m
        indices.append(idx)
    return indices

We've established that a Bloom filter can say "maybe" when the answer is actually "no." The False Positive Rate (FPR) is simply the probability that this happens. It quantifies the chance of a wrong yes.

The Mathematical Reality

You don't need to be a mathematician to understand the formula, but you should know the variables. The FPR depends on three things:

• m: The size of your bit array (how many coins you have).
• n: The number of items you add (how many times you flip coins).
• k: The number of hash functions (how many coins you flip per item).

Intuition: The Coin Flip Game

Let's make this concrete. Imagine a table full of coins (the bit array).

• Initial State: All coins are Tails (0).
• Adding an Item: You flip k random coins to Heads (1).
• Checking an Item: You check k specific coins. If all are Heads, you say "Maybe." If even one is Tails, you say "Definitely Not."

A False Positive happens when a new item (one you never added) happens to check k coins that were flipped to Heads by other items.

How to calculate the optimal settings

You rarely compute the FPR formula by hand at runtime. Instead, you use it during the design phase. If you know you plan to store n items and you have a memory budget of m bits, you can calculate the optimal number of hash functions to minimize errors:

This tells you the "sweet spot." If you use fewer hash functions than this, you waste space. If you use more, you fill the array too fast and increase false positives.

Now that we understand the theory, let's build the engine. Designing a Bloom filter is surprisingly simple because it relies on just two core operations: adding an item and checking for an item.

Algorithm design steps

Imagine you are setting up a giant chalkboard (the bit array). It's your only memory. You have a set of distinct chalks (hash functions).

Step-by-step mental model

Here is the logic you need to implement in your code. Notice how clean it is.

This logic translates directly into Python code. Notice the simplicity:

def add(self, item):
    # For every hash function we have...
    for i in range(self.num_hashes):
        # Get a hash value, modulo the array size
        index = self._hash(item, i) % self.size
        # Turn the bit ON
        self.bit_array[index] = 1

def might_contain(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i) % self.size
        # If we find a single 0, the item is NOT here
        if self.bit_array[index] == 0:
            return False
    # If we see only 1s, it MIGHT be here
    return True

Algorithm complexity analysis

Why is this so popular? It's all about efficiency.

Theory is great, but code is where the magic happens. Let's build a Bloom filter from scratch. We will implement the three core steps: Creating the array, Adding items, and Checking membership.

Step 1: Create Bit Array

The foundation is the bit array. In Python, this is just a list of integers (0s). In languages like C or Java, this might be a byte array or a `BitSet`. The key is that every single bit must start at 0.

def __init__(self, size, num_hashes):
    self.size = size
    self.num_hashes = num_hashes
    # All bits start at 0. This is critical!
    self.bit_array = [0] * size

Step 2: Add Elements (Insert)

When you add an item, you don't store the item itself. You calculate k indices using your hash functions and flip the bits at those positions to 1.

def add(self, item):
    for i in range(self.num_hashes):
        # Calculate index using hash function i
        index = self._hash(item, i) % self.size
        # Set the bit to 1
        self.bit_array[index] = 1

Step 3: Check Membership (Query)

This is the most critical part. You re-calculate the same k indices.

• If any of the bits at those indices is 0, you can immediately return False. The item was never added.
• If all bits are 1, you return True (meaning "Maybe").

def might_contain(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i) % self.size
        # If we find a single 0, it's definitely NOT here
        if self.bit_array[index] == 0:
            return False
    # If we see only 1s, it MIGHT be here
    return True

Now we arrive at the "killer feature" of Bloom filters: Space Efficiency. Why would a system choose a probabilistic structure over a standard one? The answer is almost always memory.

Intuition: Compressing Information

Think of a Bloom filter like a crowd-sourced fingerprint.

In a Hash Set, every person (item) gets their own locker (memory address) to store their identity. In a Bloom filter, everyone just leaves a mark on a giant shared wall. If you see a mark, you know someone was there. Because many people leave marks on the same spots (collisions), the wall stays relatively small compared to the number of people.

The cost? Sometimes a new person looks at the wall, sees marks that weren't made by them, and thinks "Oh, I must have been here." That's the false positive. But the wall (memory) stays tiny.

The Trade-off Formula

The relationship between space ($m$), items ($n$), and error ($p$) is governed by this formula:

This tells us that to halve your error rate, you need to add a fixed number of bits per item. You don't need to memorize the math, but you should understand the curve:

• Diminishing Returns: Dropping the error from 10% to 1% is cheap. Dropping it from 0.01% to 0.001% requires a massive increase in memory.
• Design Phase: You usually decide your budget (e.g., "I have 500MB RAM") and your acceptable error (e.g., "I can tolerate 1% mistakes") before you build.

When to Choose Bloom Filters

Bloom filters aren't a magic bullet for everything. They are a specialized tool for specific scenarios.

In summary, a Bloom filter is a pre-filter. It's the bouncer at the club who checks the list. If you're not on the list (Definitely Not), you go home. If you are on the list (Maybe), you get to talk to the manager (Database) to prove you're real.

You now have a working Bloom filter. But in production, you need to tune it. We are moving from "How it works" to "How to make it perfect for your specific data."

import math

def optimal_k(m, n):
    # m = bit array size, n = expected items
    # ln(2) is approx 0.693
    return max(1, int(round((m / n) * math.log(2))))

// Java-like pseudocode for Atomic Add
void add(Item item) {
    for (int i = 0; i < numHashes; i++) {
        int index = hash(item, i) % size;
        int wordIndex = index / 64; // Which 64-bit word?
        int bitOffset = index % 64; // Which bit in that word?

        // Atomically set the bit without locking the whole array
        bitArray.getAndUpdate(wordIndex, word -> word | (1L << bitOffset));
    }
}

You've built the filter, tuned the math, and understood the trade-offs. Now, let's address the questions that come up in real-world engineering.