How to Build a Bloom Filter From Scratch in Python to Skip Expensive Lookups

Say you are building a web crawler and you need to answer one question millions of times a day: “have I already visited this URL?” The honest answer lives in a database or a distributed cache, and checking it means a network round trip every single time, even for the 98 percent of URLs that turn out to be brand new. A Bloom filter lets you answer “definitely not” instantly, from memory, for most of those checks, and only pay for the real lookup when there is an actual chance the URL has been seen before.

This tutorial builds a Bloom filter from scratch in Python, using nothing but the standard library. You will size it correctly using the same formulas Wikipedia documents for the data structure, measure its real false-positive rate against what the math predicts, and then deliberately overload it to watch that guarantee degrade in a live table of numbers. You will also build a Counting Bloom filter, the variant that supports deletion, and reproduce the exact bug that makes deletion dangerous: removing an item that was never really there can silently break a completely unrelated, genuinely present item. Every command below was run for real while writing this post. Nothing is invented.

What You Will Build

• A BloomFilter class built on a plain bytearray bit array, with correctly derived sizing math
• A working “double hashing” trick that turns two real hash functions into as many independent-enough hash functions as you need
• A head-to-head timing comparison: a naive lookup approach against a Bloom-filter-gated one, over a realistic 98 percent-new workload
• Proof that the filter never produces a false negative, plus a measured false-positive rate checked against the exact theoretical prediction for the numbers in use
• A live demonstration of what happens when you insert far more items than the filter was sized for
• A CountingBloomFilter that supports remove(), plus a deterministic, reproduced example of the corruption bug that makes removal risky
• A real memory comparison against a plain Python set
• A pytest suite that verifies all of the above deterministically

Prerequisites

• Python 3.10 or newer (this tutorial used Python 3.13.14 on Windows; nothing here is platform-specific)
• Comfort with basic Python: classes, generators, and reading a small amount of hashing code
• No prior knowledge of Bloom filters, hashing theory, or probability is assumed; all of it is explained from first principles below

Step 1: Understand the Problem a Bloom Filter Solves

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that answers one question: is this item possibly in a set, or definitely not? It was invented for exactly the situation described above: a huge amount of source data (Bloom’s own example was a 500,000-word dictionary) where checking membership the “conventional” way would require either an impractical amount of memory or an expensive lookup, like a disk read, for every single check.

The tradeoff that makes this possible is a deliberate loss of certainty in one direction only. A Bloom filter can tell you “definitely not in the set” with total confidence. It can never tell you “definitely in the set” with total confidence, only “possibly in the set.” Occasionally it will say “possibly” about something that was never added at all; that is a false positive. What it will never do is say “definitely not” about something that actually was added; a Bloom filter is not allowed to produce a false negative, ever. That asymmetry is the entire design: you get to skip expensive work for every “definitely not,” and you only pay the real cost of a lookup on the much smaller number of “possibly” results, some of which turn out to be wrong.

Under the hood, a Bloom filter is just a bit array of m bits, all starting at 0, paired with k independent hash functions. To add an item, you run it through all k hash functions and set the bit at each resulting position to 1. To check membership, you run the item through the same k hash functions and look at those same positions: if any of them is still 0, the item was definitely never added, because adding it would have set that bit. If all k bits are 1, the item was probably added, but you cannot be certain; another combination of other items could have set those exact same bits by coincidence.

Step 2: Set Up Your Environment

Create a project folder and an isolated virtual environment. The Bloom filter implementation itself needs nothing beyond the standard library; you only need an external package for the test suite at the end.

mkdir bloom-filter-demo
cd bloom-filter-demo
python -m venv venv
venv\Scripts\activate   # on Linux/macOS: source venv/bin/activate
pip install pytest

This tutorial was written against pytest 9.1.1. The core BloomFilter code uses only hashlib and math from the standard library, so it will behave identically on any reasonably current Python 3.

Step 3: Build the Bit Array Core

Create bloom_filter.py. Start with the constructor and the low-level bit operations: a Python bytearray gives you exactly the mutable byte-addressable storage you need, and you address individual bits inside it with a little arithmetic.

import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        if expected_items <= 0:
            raise ValueError("expected_items must be positive")
        if not (0 < false_positive_rate < 1):
            raise ValueError("false_positive_rate must be between 0 and 1")

        self.expected_items = expected_items
        self.false_positive_rate = false_positive_rate

        # m = -(n * ln(p)) / (ln(2) ** 2)
        self.num_bits = math.ceil(
            -(expected_items * math.log(false_positive_rate)) / (math.log(2) ** 2)
        )
        # k = (m / n) * ln(2)
        self.num_hashes = max(1, round((self.num_bits / expected_items) * math.log(2)))

        self.bit_array = bytearray((self.num_bits + 7) // 8)
        self.items_added = 0

    def _get_bit(self, pos: int) -> bool:
        byte_index, bit_index = divmod(pos, 8)
        return bool(self.bit_array[byte_index] & (1 << bit_index))

    def _set_bit(self, pos: int) -> None:
        byte_index, bit_index = divmod(pos, 8)
        self.bit_array[byte_index] |= 1 << bit_index

Storing m bits in a bytearray of ceil(m / 8) bytes means every bit costs exactly one bit of real memory, not one Python object. divmod(pos, 8) converts a bit position into a byte index and an offset inside that byte in one call; 1 << bit_index builds a single-bit mask, and the bitwise & and |= operators read and set that one bit without disturbing its seven neighbors.

Hashing With Only Two Real Hash Functions

A naive implementation would want k genuinely different hash functions. Writing and maintaining seven or eight independent hash functions by hand is impractical, and it turns out to be unnecessary. Wikipedia’s Bloom filter article documents a standard shortcut: for a good hash function with a wide output, there is little correlation between different parts of that output, so you can synthesize as many hash functions as you need from just two real ones. The specific technique used here, which Wikipedia’s article attributes to Dillinger and Manolios (2004b), computes each of the k positions as a linear combination of two independent hashes:

    def _positions(self, item: str):
        data = item.encode("utf-8")
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
        for i in range(self.num_hashes):
            yield (h1 + i * h2) % self.num_bits

hashlib.sha256 and hashlib.md5 are two different, independent hash algorithms, both available in the Python standard library’s hashlib module, which implements the FIPS secure hash algorithms alongside legacy algorithms like MD5. Taking the first 8 bytes of each digest and converting them to an integer gives two large, well-distributed numbers, h1 and h2. The formula (h1 + i * h2) % m, run for i from 0 to k - 1, produces k positions that behave, for false-positive-rate purposes, almost as well as k fully independent hash functions would, at a fraction of the implementation cost. Note that this is a general-purpose engineering trick, not a cryptographic one: MD5 is unsuitable for security-sensitive hashing, but nothing here relies on MD5’s broken collision resistance, only on its speed and its output looking uniformly distributed.

Finish the class with add() and the membership test:

    def add(self, item: str) -> None:
        for pos in self._positions(item):
            self._set_bit(pos)
        self.items_added += 1

    def __contains__(self, item: str) -> bool:
        return all(self._get_bit(pos) for pos in self._positions(item))

Implementing __contains__ is what lets you write "some_item" in my_filter instead of a separate might_contain() method; Python calls it automatically for the in operator.

Step 4: Size the Filter Correctly

The constructor above already implements the sizing math, but it is worth seeing where it comes from and confirming it against the reference numbers. Wikipedia’s Bloom filter article gives the false-positive probability as a function of the array size m, item count n, and hash count k, and shows that for a given m and n, the value of k that minimizes that probability is k = (m / n) * ln(2). Substituting that optimal k back into the false-positive formula and solving for m gives the bit-array size needed for a target false-positive rate p: m = -(n * ln(p)) / (ln(2) ** 2). Those are exactly the two formulas in the constructor above.

Run it once to see the sizing in action:

python -c "from bloom_filter import BloomFilter; bf = BloomFilter(10_000, 0.01); print(bf.num_bits, bf.num_hashes, len(bf.bit_array), bf.num_bits / bf.expected_items)"

95851 7 11982 9.5851

For 10,000 expected items at a 1 percent target false-positive rate, the formula lands on a 95,851-bit array (11,982 bytes) and 7 hash functions, which works out to 9.59 bits per item. Wikipedia’s own article gives the same figure as a rule of thumb: “a Bloom filter with a 1% error and an optimal value of k, in contrast, requires only about 9.6 bits per element, regardless of the size of the elements,” adding that the 1 percent rate can be cut by a further factor of ten for only about 4.8 more bits per element. Nine and a half bits, rounding to the nearest byte, is a little over one byte per item, no matter how long the actual strings you are storing are. That size independence from the item content is the other half of why Bloom filters are so compact: a Python set has to store the actual strings, but a Bloom filter only ever stores which bits got flipped.

Step 5: See Why It Is Worth It

Numbers on their own are not convincing. Build a small simulation of the crawler scenario from Step 1: a store of 50,000 already-seen URLs, a slow “lookup” function that stands in for a real database round trip, and a batch of 2,000 candidate URLs where only 2 percent are genuine repeats. Create demo1_motivation.py:

import random
import string
import time

from bloom_filter import BloomFilter


def make_url(rng: random.Random) -> str:
    path = "".join(rng.choices(string.ascii_lowercase + string.digits, k=12))
    return f"https://example.com/articles/{path}"


def slow_lookup(seen_store: set, url: str) -> bool:
    """Stands in for a real disk/network round trip, e.g. a database SELECT."""
    time.sleep(0.001)
    return url in seen_store


def naive_check(seen_store: set, candidates: list) -> tuple:
    start = time.perf_counter()
    new_urls = [u for u in candidates if not slow_lookup(seen_store, u)]
    return new_urls, time.perf_counter() - start


def bloom_gated_check(seen_store: set, bf: BloomFilter, candidates: list) -> tuple:
    start = time.perf_counter()
    new_urls = []
    slow_calls = 0
    for u in candidates:
        if u in bf:
            slow_calls += 1
            if not slow_lookup(seen_store, u):
                new_urls.append(u)
        else:
            new_urls.append(u)
    return new_urls, time.perf_counter() - start, slow_calls


if __name__ == "__main__":
    rng = random.Random(42)

    seen_store = {make_url(rng) for _ in range(50_000)}
    bf = BloomFilter(expected_items=len(seen_store), false_positive_rate=0.01)
    for url in seen_store:
        bf.add(url)

    batch = []
    seen_list = list(seen_store)
    for _ in range(2_000):
        if rng.random() < 0.02:
            batch.append(rng.choice(seen_list))
        else:
            batch.append(make_url(rng))
    rng.shuffle(batch)

    print(f"seen_store size: {len(seen_store)}")
    print(f"batch size: {len(batch)}")

    naive_new, naive_time = naive_check(seen_store, batch)
    bloom_new, bloom_time, slow_calls = bloom_gated_check(seen_store, bf, batch)

    print(f"\nnaive approach:  {len(naive_new)} new URLs, {naive_time:.3f}s, "
          f"{len(batch)} slow_lookup calls")
    print(f"bloom-gated:     {len(bloom_new)} new URLs, {bloom_time:.3f}s, "
          f"{slow_calls} slow_lookup calls")
    print(f"\nresults match: {sorted(naive_new) == sorted(bloom_new)}")
    print(f"speedup: {naive_time / bloom_time:.1f}x")
    print(f"slow_lookup calls avoided: {len(batch) - slow_calls} "
          f"({(len(batch) - slow_calls) / len(batch) * 100:.1f}%)")

python demo1_motivation.py

seen_store size: 50000
batch size: 2000

naive approach:  1966 new URLs, 3.105s, 2000 slow_lookup calls
bloom-gated:     1966 new URLs, 0.092s, 57 slow_lookup calls

results match: True
speedup: 33.8x
slow_lookup calls avoided: 1943 (97.2%)

Both approaches agree on exactly which 1,966 URLs are new; the Bloom filter never causes a wrong answer. The naive approach pays the simulated 1-millisecond cost for every one of the 2,000 candidates, taking about 3.1 seconds. The Bloom-gated version only calls slow_lookup when the filter says “possibly present,” which happened 57 times out of 2,000, a mix of the genuine repeats and a small number of false positives, avoiding 1,943 of the 2,000 slow calls (97.2 percent) and cutting wall-clock time by 33.8x. The gap would widen further in a real system, where slow_lookup is an actual network call measured in tens of milliseconds, not one simulated millisecond.

Step 6: Verify the Core Guarantee: Zero False Negatives

The whole point of a Bloom filter is that it can never lie in the “definitely not in the set” direction. Prove that empirically, then measure exactly how often it lies in the other direction. Create demo2_false_positive_rate.py:

import random
import string

from bloom_filter import BloomFilter


def make_item(rng: random.Random) -> str:
    return "user_" + "".join(rng.choices(string.ascii_lowercase + string.digits, k=10))


if __name__ == "__main__":
    rng = random.Random(7)

    n = 10_000
    bf = BloomFilter(expected_items=n, false_positive_rate=0.01)

    members = [make_item(rng) for _ in range(n)]
    for m in members:
        bf.add(m)

    false_negatives = sum(1 for m in members if m not in bf)
    print(f"members added: {len(members)}")
    print(f"false negatives observed: {false_negatives}")

    non_members = []
    while len(non_members) < 100_000:
        candidate = make_item(rng)
        if candidate not in members:
            non_members.append(candidate)

    print(f"\nnon-members tested: {len(non_members)}")
    false_positives = sum(1 for x in non_members if x in bf)
    empirical_rate = false_positives / len(non_members)

    print(f"false positives observed: {false_positives}")
    print(f"empirical false-positive rate: {empirical_rate:.4f}")
    print(f"design target false-positive rate: {bf.false_positive_rate}")
    print(f"theoretical rate for this exact n={bf.items_added}, m={bf.num_bits}, "
          f"k={bf.num_hashes}: {bf.estimated_false_positive_rate():.4f}")
    print(f"bits set: {bf.bits_set_ratio() * 100:.1f}% "
          f"(Wikipedia: 'about half of the bits will be set' for a well-tuned filter)")

python demo2_false_positive_rate.py

members added: 10000
false negatives observed: 0

non-members tested: 100000
false positives observed: 1013
empirical false-positive rate: 0.0101
design target false-positive rate: 0.01
theoretical rate for this exact n=10000, m=95851, k=7: 0.0100
bits set: 51.8% (Wikipedia: 'about half of the bits will be set' for a well-tuned filter)

The bits_set_ratio() and estimated_false_positive_rate() helper methods used above are simple additions to the BloomFilter class from Step 3:

    def bits_set_ratio(self) -> float:
        set_bits = sum(bin(byte).count("1") for byte in self.bit_array)
        return set_bits / self.num_bits

    def estimated_false_positive_rate(self) -> float:
        """Theoretical FP rate for the actual n/m/k this filter is using right now."""
        n, m, k = self.items_added, self.num_bits, self.num_hashes
        return (1 - math.exp(-k * n / m)) ** k

Zero false negatives out of 10,000 real members: every single item you actually added is correctly reported present, exactly as the design guarantees. Across 100,000 items that were never added, 1,013 came back as false positives, an empirical rate of 1.01 percent against a 1 percent target. That is not a coincidence; it matches a more precise theoretical prediction for these exact numbers almost exactly, computed with (1 - e ** (-k * n / m)) ** k using the actual n, m, and k this filter ended up with. The 51.8 percent bit-occupancy figure also lines up with a property Wikipedia’s article calls out directly: when k and m are chosen well, about half of the bits end up set, which is the point at which the array carries the maximum information for its size.

Step 7: The Gotcha: What Happens When You Outgrow Your Filter

Every one of those numbers assumed you insert roughly as many items as you told the constructor to expect. Nothing stops you from inserting more, and nothing errors when you do; the filter just quietly gets worse. Create demo3_saturation.py to make that visible:

import random
import string

from bloom_filter import BloomFilter


def make_item(rng: random.Random, prefix: str) -> str:
    return prefix + "".join(rng.choices(string.ascii_lowercase + string.digits, k=10))


def measure_fp_rate(bf: BloomFilter, rng: random.Random, inserted: set, trials: int = 20_000) -> float:
    non_members = []
    while len(non_members) < trials:
        candidate = make_item(rng, "probe_")
        if candidate not in inserted:
            non_members.append(candidate)
    false_positives = sum(1 for x in non_members if x in bf)
    return false_positives / trials


if __name__ == "__main__":
    rng = random.Random(99)
    capacity = 10_000
    bf = BloomFilter(expected_items=capacity, false_positive_rate=0.01)

    print(f"filter sized for capacity={capacity}, target false-positive rate=0.01")
    print(f"num_bits={bf.num_bits} num_hashes={bf.num_hashes}\n")

    inserted = set()
    checkpoints = [capacity, capacity * 2, capacity * 5, capacity * 10]
    checkpoint_idx = 0

    print(f"{'items_added':>12} {'load (n/capacity)':>18} {'theoretical_fp':>15} {'empirical_fp':>14}")
    for i in range(checkpoints[-1]):
        item = make_item(rng, "item_")
        bf.add(item)
        inserted.add(item)
        if bf.items_added == checkpoints[checkpoint_idx]:
            empirical = measure_fp_rate(bf, rng, inserted)
            theoretical = bf.estimated_false_positive_rate()
            load = bf.items_added / capacity
            print(f"{bf.items_added:>12} {load:>18.1f} {theoretical:>15.4f} {empirical:>14.4f}")
            checkpoint_idx += 1
            if checkpoint_idx >= len(checkpoints):
                break

python demo3_saturation.py

filter sized for capacity=10000, target false-positive rate=0.01
num_bits=95851 num_hashes=7

 items_added  load (n/capacity)  theoretical_fp   empirical_fp
       10000                1.0          0.0100         0.0107
       20000                2.0          0.1575         0.1582
       50000                5.0          0.8319         0.8330
      100000               10.0          0.9953         0.9966

At exactly the sized capacity, the filter behaves as designed: about 1 percent false positives. At twice the load, that jumps to nearly 16 percent. At five times the load, it is over 83 percent, and by ten times the load the filter says “possibly present” for 99.66 percent of everything, real or not, which makes it functionally useless: you are back to paying for almost every lookup, except now you are also paying for the filter. The empirical measurements track the theoretical prediction closely at every checkpoint, which is exactly what you want; it means the degradation is not a bug, it is the documented mathematical behavior of an under-provisioned filter. Wikipedia’s article states the underlying reason plainly: elements can be added but not removed from a plain Bloom filter, and the more items added beyond what it was sized for, the larger the probability of a false positive. In production, this means you have to either size generously up front, monitor real item counts against the design capacity, or rebuild the filter from scratch once you approach it.

Step 8: Why You Cannot Delete, and How a Counting Bloom Filter Fixes That

The bit array design has no concept of “how many things set this bit.” If two items share a bit position and you clear that bit to remove one of them, you have also silently removed the other, along with anything else that happened to touch that bit. A Counting Bloom filter fixes this by extending each array position from a single bit to a small counter, an idea that Wikipedia’s article traces to Fan et al. (2000): “In a counting filter, the array positions (buckets) are extended from being a single bit to being a multibit counter… regular Bloom filters can be considered as counting filters with a bucket size of one bit.” Adding increments the counters at the item’s positions instead of just setting bits; removing decrements them; membership still checks that every relevant counter is nonzero. Create counting_bloom_filter.py:

from array import array

from bloom_filter import BloomFilter


class CountingBloomFilter(BloomFilter):
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01, max_count: int = 255):
        super().__init__(expected_items, false_positive_rate)
        self.max_count = max_count
        self.counters = array("B", [0]) * self.num_bits

    def add(self, item: str) -> None:
        for pos in self._positions(item):
            if self.counters[pos] < self.max_count:
                self.counters[pos] += 1
        self.items_added += 1

    def __contains__(self, item: str) -> bool:
        return all(self.counters[pos] > 0 for pos in self._positions(item))

    def remove(self, item: str) -> None:
        for pos in self._positions(item):
            if self.counters[pos] > 0:
                self.counters[pos] -= 1
        self.items_added = max(0, self.items_added - 1)

The array("B", ...) call builds a compact array of unsigned single-byte counters, one per bit position, capped at 255 by max_count so a counter can never silently wrap around back to zero. A production system tracking items with very high overlap on the same positions would want to watch for that cap being hit; this implementation simply stops incrementing rather than overflowing, which avoids corruption at the cost of a filter that can get slightly less accurate under extreme skew. Confirm the basic add, remove, and re-add cycle works, and that removing one item leaves an unrelated one untouched:

cbf = CountingBloomFilter(expected_items=10_000, false_positive_rate=0.01)
cbf.add("session_alice")
cbf.add("session_bob")
print("session_alice" in cbf, "session_bob" in cbf)
cbf.remove("session_alice")
print("session_alice" in cbf, "session_bob" in cbf)

True True
False True

The Real Danger: Removing Something That Was Never There

That looks safe, but the counting filter’s contract has a sharp edge: remove() only behaves correctly if the item you are removing was actually added. Nothing stops you from calling it on an item that merely tests as a false positive, and doing so decrements real counters that a genuinely present item still depends on. Reproduce this deterministically with a small filter, so a shared position is easy to force and easy to see. Create demo4_counting_corruption.py:

from counting_bloom_filter import CountingBloomFilter


if __name__ == "__main__":
    cbf = CountingBloomFilter(expected_items=5, false_positive_rate=0.1)
    print(f"tiny filter for this demo: num_bits={cbf.num_bits} num_hashes={cbf.num_hashes}\n")

    item_a = "session_alice_7f3e9c"
    item_b = "session_bob_2d81ac"
    cbf.add(item_a)
    cbf.add(item_b)

    positions_a = set(cbf._positions(item_a))
    positions_b = set(cbf._positions(item_b))
    print(f"'{item_a}' occupies positions {sorted(positions_a)}")
    print(f"'{item_b}' occupies positions {sorted(positions_b)}")
    print(f"counters now: {list(cbf.counters)}")

    # Search for a phantom string: never added, but (a) tests as a false
    # positive right now, and (b) shares at least one position with item_a
    # or item_b where that position's counter is currently exactly 1, so
    # removing the phantom would zero out a counter a real member needs.
    phantom = None
    for i in range(200_000):
        candidate = f"probe_{i}"
        if candidate in (item_a, item_b):
            continue
        cand_positions = set(cbf._positions(candidate))
        is_false_positive = all(cbf.counters[p] > 0 for p in cand_positions)
        if not is_false_positive:
            continue
        fragile_positions = {p for p in cand_positions if cbf.counters[p] == 1}
        if fragile_positions & (positions_a | positions_b):
            phantom = candidate
            break

    phantom_positions = set(cbf._positions(phantom))
    print(f"\nfound phantom '{phantom}' after searching probe strings")
    print(f"'{phantom}' in cbf: {phantom in cbf}  (never added, but tests positive)")
    print(f"'{phantom}' occupies positions {sorted(phantom_positions)}")
    print(f"overlap with item_a positions: {sorted(phantom_positions & positions_a)}")
    print(f"overlap with item_b positions: {sorted(phantom_positions & positions_b)}")

    print(f"\nbefore removing the phantom:")
    print(f"  '{item_a}' in cbf: {item_a in cbf}")
    print(f"  '{item_b}' in cbf: {item_b in cbf}")

    cbf.remove(phantom)  # phantom was never added; this should never happen in
                          # correct code, but nothing stops you from calling it

    print(f"\nafter cbf.remove('{phantom}') on an item that was NEVER added:")
    print(f"  counters now: {list(cbf.counters)}")
    print(f"  '{item_a}' in cbf: {item_a in cbf}")
    print(f"  '{item_b}' in cbf: {item_b in cbf}")

python demo4_counting_corruption.py

tiny filter for this demo: num_bits=24 num_hashes=3

'session_alice_7f3e9c' occupies positions [5, 16, 18]
'session_bob_2d81ac' occupies positions [1, 19, 22]
counters now: [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0]

found phantom 'probe_76' after searching probe strings
'probe_76' in cbf: True  (never added, but tests positive)
'probe_76' occupies positions [1]
overlap with item_a positions: []
overlap with item_b positions: [1]

before removing the phantom:
  'session_alice_7f3e9c' in cbf: True
  'session_bob_2d81ac' in cbf: True

after cbf.remove('probe_76') on an item that was NEVER added:
  counters now: [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0]
  'session_alice_7f3e9c' in cbf: True
  'session_bob_2d81ac' in cbf: False

The string "probe_76" was never added to this filter. It happens to hash to position 1, the same position session_bob_2d81ac hashes to, and position 1’s counter was sitting at exactly 1, meaning only session_bob_2d81ac was relying on it. Because "probe_76" tests as present (a genuine, expected false positive on a filter this small), nothing in the code stops cbf.remove("probe_76") from running. That call decrements position 1 back to zero, and session_bob_2d81ac, an item that really was added and never removed, now incorrectly reports as absent. That is a real false negative, the one outcome a Bloom filter is supposed to make impossible, and it happened purely because remove() was called on something that merely looked like a member. The practical rule this forces on you: only ever call remove() on items you have independent, authoritative proof were actually added, for example because you are also tracking them in the real backing store. If you cannot guarantee that, do not offer deletion at all, or accept the corruption risk and rebuild the filter periodically instead.

Step 9: Is It Worth the Tradeoff? A Real Memory Comparison

All of this complexity buys you something concrete: space. Compare the real memory footprint of a Python set holding a million strings against the equivalent Bloom filter. Create demo5_memory.py:

import sys

from bloom_filter import BloomFilter


def real_set_size_bytes(items: list) -> int:
    s = set(items)
    container = sys.getsizeof(s)
    strings = sum(sys.getsizeof(item) for item in s)
    return container + strings


if __name__ == "__main__":
    items = [f"user_{i:08d}@example.com" for i in range(1_000_000)]

    set_bytes = real_set_size_bytes(items)

    bf = BloomFilter(expected_items=len(items), false_positive_rate=0.01)
    for item in items:
        bf.add(item)
    bloom_bytes = sys.getsizeof(bf.bit_array)

    print(f"items: {len(items):,}")
    print(f"python set:   {set_bytes:,} bytes ({set_bytes / 1024 / 1024:.1f} MiB)")
    print(f"bloom filter: {bloom_bytes:,} bytes ({bloom_bytes / 1024 / 1024:.1f} MiB)")
    print(f"ratio: set uses {set_bytes / bloom_bytes:.1f}x more memory")

python demo5_memory.py

items: 1,000,000
python set:   99,554,648 bytes (94.9 MiB)
bloom filter: 1,198,190 bytes (1.1 MiB)
ratio: set uses 83.1x more memory

One million email-shaped strings cost 94.9 MiB in a real Python set, counting both the container overhead and every string object it holds. The Bloom filter sized for the same million items at the same 1 percent false-positive rate costs 1.1 MiB, an 83.1x reduction. That gap is the entire reason this data structure exists: you are trading the ability to say exactly what is in the set, and a small, tunable, one-directional chance of being wrong, for close to two orders of magnitude less memory.

Step 10: Write a Verification Test Suite

Turn the properties you just demonstrated by hand into a suite you can run on every change. Create test_bloom_filter.py:

import random
import string

import pytest

from bloom_filter import BloomFilter
from counting_bloom_filter import CountingBloomFilter


def random_items(n, seed=0, prefix="item_"):
    rng = random.Random(seed)
    return [prefix + "".join(rng.choices(string.ascii_lowercase + string.digits, k=12))
            for _ in range(n)]


def test_never_produces_a_false_negative():
    items = random_items(5_000, seed=1)
    bf = BloomFilter(expected_items=len(items), false_positive_rate=0.01)
    for item in items:
        bf.add(item)
    for item in items:
        assert item in bf, f"false negative for {item!r}, this must never happen"


def test_empirical_false_positive_rate_is_close_to_target():
    members = random_items(5_000, seed=2, prefix="member_")
    non_members = random_items(20_000, seed=3, prefix="stranger_")
    bf = BloomFilter(expected_items=len(members), false_positive_rate=0.01)
    for item in members:
        bf.add(item)
    false_positives = sum(1 for x in non_members if x in bf)
    rate = false_positives / len(non_members)
    assert rate < 0.02, f"empirical FP rate {rate:.4f} is more than 2x the 0.01 target"


def test_rejects_invalid_constructor_args():
    with pytest.raises(ValueError):
        BloomFilter(expected_items=0)
    with pytest.raises(ValueError):
        BloomFilter(expected_items=10, false_positive_rate=1.0)


def test_counting_filter_remove_then_readd():
    cbf = CountingBloomFilter(expected_items=1_000, false_positive_rate=0.01)
    cbf.add("token_a")
    assert "token_a" in cbf
    cbf.remove("token_a")
    assert "token_a" not in cbf
    cbf.add("token_a")
    assert "token_a" in cbf


def test_counting_filter_remove_does_not_affect_other_members():
    cbf = CountingBloomFilter(expected_items=1_000, false_positive_rate=0.01)
    items = random_items(200, seed=4)
    for item in items:
        cbf.add(item)
    cbf.remove(items[0])
    assert items[0] not in cbf
    for item in items[1:]:
        assert item in cbf, f"removing {items[0]!r} incorrectly evicted {item!r}"

python -m pytest test_bloom_filter.py -v

collected 5 items

test_bloom_filter.py::test_never_produces_a_false_negative PASSED        [ 20%]
test_bloom_filter.py::test_empirical_false_positive_rate_is_close_to_target PASSED [ 40%]
test_bloom_filter.py::test_rejects_invalid_constructor_args PASSED       [ 60%]
test_bloom_filter.py::test_counting_filter_remove_then_readd PASSED      [ 80%]
test_bloom_filter.py::test_counting_filter_remove_does_not_affect_other_members PASSED [100%]

5 passed in 0.11s

Common Mistakes and Gotchas

• Sizing the filter for today’s data, not tomorrow’s. Step 7 showed a filter at 2x its designed capacity already failing 1 request in 6. Size for your expected peak, not your current count, and monitor real inserted-item counts against that budget.
• Treating remove() as always safe on a Counting Bloom filter. It is only safe on items you know for certain were added. Removing anything else, including an ordinary false positive, can corrupt a real member’s counters, as demonstrated in Step 8.
• Forgetting a Bloom filter cannot enumerate its contents. It answers “might this be in the set,” never “what is in the set.” If you need the latter, you still need a real index alongside it.
• Ignoring the counter overflow ceiling on a counting filter. This implementation caps counters at 255 and simply stops incrementing past that point rather than wrapping around to zero, which avoids silent corruption but means extremely skewed data (many items sharing very few positions) can quietly reduce accuracy. Watch for it if your data has that shape.
• Reaching for Python’s built-in hash() instead of a stable hash like hashlib.sha256. Python randomizes hash() output per process by default, so a filter built with it would compute different bit positions every time your program restarts, making it useless for anything persisted to disk or shared across processes. The consistent hashing tutorial on this site walks through that exact gotcha in more detail.

Where Bloom Filters Show Up in Real Systems

This is not a purely academic exercise. Apache Cassandra’s storage engine documentation explains that Cassandra uses Bloom filters when accessing data from its on-disk SSTable files specifically to enhance read performance, avoiding an expensive disk read when a query is looking for a partition key that provably does not exist in a given SSTable. PostgreSQL ships an official bloom extension that builds an index access method directly on the same idea: its documentation describes a Bloom index as “a lossy representation of the indexed attribute(s)… prone to reporting false positives,” useful specifically for fast exclusion of non-matching rows across tables with many columns and unpredictable query combinations, with every match still rechecked against the real row before being trusted. Both systems make the same trade this tutorial just built by hand: a small, tunable chance of a wasted check, in exchange for skipping the overwhelming majority of expensive ones.

How to Verify Everything Works End to End

Confirm the whole tutorial holds together by running every script in sequence from a clean checkout:

python bloom_filter.py
python demo1_motivation.py
python demo2_false_positive_rate.py
python demo3_saturation.py
python counting_bloom_filter.py
python demo4_counting_corruption.py
python demo5_memory.py
python -m pytest test_bloom_filter.py -v

You should see: a sizing summary matching roughly 9.6 bits per element, a large speedup with matching results between the naive and Bloom-gated approaches, zero false negatives with an empirical false-positive rate close to your target, a saturation table where the false-positive rate climbs sharply past 1x load, a correct add/remove/re-add cycle for the counting filter, a reproduced false negative caused by removing a phantom item, an 80x-plus memory reduction versus a plain set, and five passing tests. Because the timing numbers depend on your machine and the false-positive and phantom-search numbers depend on the random seeds used, your exact figures will vary slightly from the ones shown here, but the shape of every result, zero false negatives, a false-positive rate near the target, sharp degradation past capacity, and reproducible corruption from unsafe removal, should hold every time.

Next Steps

A plain Bloom filter is the simplest member of a larger family of probabilistic data structures. If you need to remove items without the corruption risk demonstrated in Step 8, look at Cuckoo filters, which support deletion natively by design rather than through counters. If you need to estimate the number of distinct items in a huge stream rather than test membership, look at HyperLogLog. If your data set keeps growing and you cannot pick a fixed capacity up front, look at Scalable Bloom filters, which add new, appropriately sized filters as the existing ones fill up instead of degrading the way Step 7 showed. For related hands-on material already on this site, see the consistent hashing tutorial for another hash-based data structure built from scratch, and the perceptual hashing tutorial for a different real-world application of comparing hash outputs instead of raw data.