15.2 Bloom Filters

Prerequisites: Hash Tables and bit operations. A Bloom filter answers probabilistic membership queries: it can definitively say "never seen before," but can only indicate "possibly seen before."

The List Is Too Long: Answers Can Be Slightly Fuzzy

At the exit of the algorithm forest, there's a list validation checkpoint. Storing every name exactly as it appears would be most accurate, but the gatekeeper only wants to block clearly out-of-list requests. A small number of "possibly matching" results can be verified later against the backend database.

A Bloom filter stores a set summary using m bits and k hash positions. When an element is added, the corresponding positions are set to 1. During a query, if any position is 0, the element is definitively not present. If all positions are 1, the element may have been added, or it may have been accidentally covered by another element.

As a result, standard Bloom filters come with two asymmetric guarantees:

• No false negatives, provided no deletions occur, the bit array remains intact, and the encoding and hash configuration stay consistent;
• Allows false positives, caller must be prepared to perform a secondary verification.

The Gatekeeper's Bit Registry

The gatekeeper does not store passengers' full names; instead, it marks only specific positions on a bit board. During a query, if any position remains 0, the passenger is definitively unregistered. Only when all positions are 1 can the passenger be forwarded for verification against the authoritative registry. The following implementation enforces this rule using actual bits, rather than substituting the spatial model with set.

We use bytearray, where each byte holds 8 positions. The interface accepts only bytes, allowing the caller to determine character encoding; when used across services, the digest algorithm, bit count, hash count, and serialization version must be fixed.

import hashlib


class BloomFilter:
    def __init__(self, bit_count, hash_count):
        if not isinstance(bit_count, int) or bit_count <= 0:
            raise ValueError("bit_count must be a positive integer")
        if not isinstance(hash_count, int) or hash_count <= 0:
            raise ValueError("hash_count must be a positive integer")
        self.bit_count = bit_count
        self.hash_count = hash_count
        self._bits = bytearray((bit_count + 7) // 8)

    def _positions(self, value):
        if not isinstance(value, bytes):
            raise TypeError("BloomFilter values must be bytes")
        digest = hashlib.blake2b(value, digest_size=16).digest()
        first = int.from_bytes(digest[:8], "little")
        second = int.from_bytes(digest[8:], "little") | 1
        for index in range(self.hash_count):
            yield (first + index * second) % self.bit_count

    def add(self, value):
        for position in self._positions(value):
            byte_index, bit_index = divmod(position, 8)
            self._bits[byte_index] |= 1 << bit_index

    def might_contain(self, value):
        for position in self._positions(value):
            byte_index, bit_index = divmod(position, 8)
            if not self._bits[byte_index] & (1 << bit_index):
                return False
        return True

    def byte_size(self):
        return len(self._bits)


if __name__ == "__main__":
    bloom = BloomFilter(bit_count=10_000, hash_count=7)
    inserted = [f"traveler-{index}".encode() for index in range(500)]
    for item in inserted:
        bloom.add(item)

    assert all(bloom.might_contain(item) for item in inserted)
    assert bloom.byte_size() == 1_250

    probes = [f"outsider-{index}".encode() for index in range(2_000)]
    false_positives = sum(bloom.might_contain(item) for item in probes)
    print("Number of false positives in sample", false_positives)

The final false positive count is merely a measurement from this batch of probes, it does not provide probabilistic guarantees. The actual test must assert: every inserted element returns True.

The More Names on the List, the More Likely the Gatekeeper Makes a Mistake

The size of the bit array m, the number of entries n, and the number of marks placed per name k jointly determine false positives. Adding more marks initially helps, but once too many are drawn, the entire panel quickly becomes cluttered.

After inserting n elements, under a hash model that is approximately independent and uniformly distributed, the false positive rate is approximately:

p ≈ (1 - exp(-k * n / m))^k

Given m and the expected value of n, the number of hash functions needed to keep the false positive rate low is approximately:

k ≈ (m / n) * ln(2)

k is not better the larger it is. Too few hash positions result in underutilized bits; too many make each operation more expensive and fill the bit array faster. Capacity planning should be derived from the expected number of elements and the acceptable false positive rate, not arbitrarily set to k=3.

Actual false positive rates are also influenced by hash quality, input distribution, and capacity overflow. Once the number of elements significantly exceeds the design capacity, more and more bits turn to 1, and the filter gradually loses its ability to distinguish between entries. Production systems typically monitor the fill rate and schedule generational replacement or full rebuilds.

Why You Shouldn't Just Erase a Mark Arbitrarily

Two travelers might leave a mark in the same cell. If the gatekeeper removes the mark to eliminate one of them, the other traveler will be incorrectly flagged as absent. Shared bits do not track ownership.

A single bit might be set to 1 by multiple elements. When one element is deleted and those bits are cleared, other elements may be falsely identified as non-existent. Counting Bloom filters store counts at each position and support deletion under certain constraints, but they require more space and must handle count overflow and concurrent updates.

If the requirement is for exact membership, enumeration of elements, or strict consistency after deletion, use sets, hash tables, or other indexing structures. Bloom filters are best used before authoritative data sources to reduce invalid queries, they cannot replace authoritative data.

Complexity and Engineering Boundaries

Operation	Time	Space or Error
Insert	O(k)	Sets k bits
Query	O(k)	May produce false positives
Store	O(m) bits	Does not preserve original elements

A summary computation also requires reading the input bytes; a strict formulation should include O(L), where L is the input length. This page uses a 128-bit hash to perform double hashing and generate multiple positions (a common engineering compromise) does not equate to achieving k mathematically independent hash functions.

Hands-on Measuring Filters

1. Fix n and m, vary k, and compare the measured false alarm rate with the approximate formula.
2. Insert a quantity exceeding the design value by a factor of two, and record the bit padding rate along with changes in false alarm rate.
3. Add a version number to the configuration and design a cross-version serialization format.
4. Explain why, after might_contain returns True, access to authoritative storage is still required.
5. Design an example where a direct bit-clearing deletion operation could produce a false negative.

The Gatekeeper's Next Map

A Bloom filter trades in false positives for compact space. The next topic, Union-Find, rejects probabilistic answers entirely, instead maintaining a continuously merging set of connected components. The following lesson uses Segment Trees to handle interval aggregation and point updates.