15.2 Bloom Filters

Prerequisites: Hash Tables and bit operations. A Bloom filter answers probabilistic membership queries: a negative result means “not inserted,” while a positive result means “possibly inserted.”

The List Is Too Long: Answers Can Be Slightly Fuzzy

Suppose a backend wants to reject keys that are definitely absent before sending the remaining “possibly present” cases to an authoritative database. Storing every key gives exact answers but costs more space; a Bloom filter chooses a different contract.

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 insertion is fully applied, no bit updates are lost or corrupted, and encoding and hash configuration stay consistent;
• False positives are allowed; callers must be prepared to perform a secondary verification.

How a Bit Array Represents a Set Summary

The filter does not store complete keys. It maps each key to several positions in a bit array. If any queried bit is 0, the key was not added under the same configuration; if every bit is 1, the caller must still check the authoritative data source. The implementation below uses real bits rather than substituting a set and changing the space model.

We use bytearray, where each byte holds 8 positions. The interface accepts only bytes, leaving character encoding to the caller. This implementation requires a positive power-of-two bit count m and a hash count from 1 through m, rejecting boolean configurations. Bloom filters in general do not require power-of-two sizes. This restriction makes the odd double-hash step coprime with m, preventing the first k positions from cycling early. Cross-service use must fix the digest algorithm, byte order, bit count, hash count, and serialization version. Configuration remains unchanged after construction.

import hashlib

class BloomFilter:
    def __init__(self, bit_count, hash_count):
        if (not isinstance(bit_count, int) or isinstance(bit_count, bool)
                or bit_count <= 0 or bit_count & (bit_count - 1)):
            raise ValueError("bit_count must be a positive power of two")
        if (not isinstance(hash_count, int) or isinstance(hash_count, bool)
                or not 1 <= hash_count <= bit_count):
            raise ValueError("hash_count must be an integer in [1, bit_count]")
        self._bit_count = bit_count
        self._hash_count = hash_count
        self._bits = bytearray((bit_count + 7) // 8)

    @property
    def bit_count(self):
        return self._bit_count

    @property
    def hash_count(self):
        return self._hash_count

    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=8_192, hash_count=7)
    inserted = [f"user-{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_024

    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 false-positive count measures this probe batch; it is not a probability guarantee. Zero observed false positives do not prove a zero rate. Tests should assert that every inserted element returns True and check bit positions, an empty filter, and invalid inputs; false-positive rates need separate measurement. byte_size() counts only the bit-array payload: 1,024 bytes here, excluding Python object and allocator overhead.

A Fuller Bit Array Produces More False Positives

The bit count m, number of distinct inserted elements n, and positions per element k jointly affect false positives. Reinserting the same bytes only sets the same positions and does not increase this n.

Under independent uniform hashing, after n distinct insertions a bit remains zero with probability (1-1/m)^(kn), approximately exp(-kn/m). Approximating the joint event for query positions then gives the false-positive rate for an absent element:

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

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

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

For a target 0<p<1, substituting the approximate optimal k gives m ≈ -n*ln(p)/(ln(2)^2). Round m and k to valid integers; this implementation also rounds m up to a power of two, then recomputes k using that actual m. The model is not a hard guarantee for arbitrary inputs.

Larger k is not always better. 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 Cannot Clear a Bit Directly

Two elements may map to the same bit. Clearing that bit to delete one element can make the other element appear absent. Shared bits do not track ownership.

Counting Bloom filters retain per-position counts and can support deletion under restrictions: an element must actually have been inserted, and deletions must not outnumber insertions. A “possibly present” result alone cannot justify decrementing counts. Overflow, underflow, and lost concurrent updates can also break the guarantee, and counters use more space.

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

Reading L input bytes makes insertion and query take O(L+k) worst-case time. Construction also takes Θ(ceil(m/8)) time to initialize the array. This counts integer operations on hash positions as constant time. hashlib.blake2b produces a 128-bit digest, split into two 64-bit integers for double hashing. The resulting k positions are not mathematically independent hash functions. Kirsch and Mitzenmacher’s paper analyzes asymptotic false-positive properties of double hashing; it does not make the formula above an exact probability for this code.

An odd step guarantees coprimality when m is a power of two. Allowing m=10 with a step of 5 would visit only two positions. This implementation also has no concurrency lock: read-modify-write operations on a byte can lose another thread’s set bits. Before a negative result can justify skipping the database, all relevant committed keys must be reflected in the filter. During incomplete construction or synchronization lag, query the authoritative source.

Measure the Filter

1. Fix n and m, vary k, and compare the measured false-positive rate with the approximate formula.
2. Insert a quantity exceeding the design value by a factor of two, and record the bit fill rate along with changes in false-positive rate.
3. Add a version number to the configuration and design a cross-process 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.

Next: From Probabilistic Membership to Dynamic Connectivity

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.