Bloom Filters Explained: Space-Efficient Membership Testing

A Bloom filter is a probabilistic data structure that answers set membership queries in O(k) time and uses orders of magnitude less memory than storing the elements themselves. In exchange for that efficiency, it can occasionally say "yes" when the true answer is "no."

What Is a Bloom Filter?

A Bloom filter consists of two parts: a bit array of m bits (all initialized to 0) and k independent hash functions. Each hash function maps an element to one of the m bit positions. The filter never stores the elements themselves, only the pattern of bits their hashes produce. This makes the memory usage fixed and tiny: a filter designed for 1 million elements at a 1% false positive rate needs about 9.6 bits per element regardless of whether elements are short integers or long strings.

The trade-off is accuracy. A Bloom filter can produce false positives (reporting an element is present when it is not) but never false negatives (it will never report an element is absent if that element was actually inserted). The phrase used in practice: "Definitely not in the set, or probably in the set." This asymmetry is exactly what many applications need.

How Does Insert Work?

To add an element to a Bloom filter, run it through all k hash functions. Each function produces an index into the bit array. Set all k of those bits to 1. That is the entire insert operation — no collision resolution, no dynamic resizing, no pointer chasing. The cost is k hash computations and k bit writes.

Deletion is not supported. Once a bit is set to 1, you cannot clear it safely because that bit may also have been set by a different element's hash. Counting Bloom filters address this by storing a small integer per position instead of a single bit, allowing decrements, but at increased memory cost.

How Does Lookup Work?

To check whether an element is in the filter, hash it with all k functions and check whether all k corresponding bits are set to 1. If any bit is 0, the element was definitely not inserted. If all bits are 1, the element was probably inserted — but those bits might have been set by other elements, producing a false positive.

The probability that a specific bit is still 0 after n insertions using k hash functions in an m-bit array decreases with each insertion. This is why false positive rates increase as the filter fills up.

False Positive Rate Formula

The probability of a false positive after inserting n elements into an m-bit filter with k hash functions is approximately:

p = (1 - e^(-kn/m))^k

Where:

• m = number of bits in the array
• n = number of elements inserted
• k = number of hash functions
• e = base of the natural logarithm (2.718...)
• p = false positive probability

The optimal number of hash functions for a given m and n is k = (m/n) * ln(2), approximately 0.693 * m/n. More hash functions means each lookup is more discriminating, but also means bits fill up faster. The optimal k balances these effects.

Python Implementation

import hashlib

class BloomFilter:
    def __init__(self, size: int, num_hashes: int):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = bytearray(size)

    def _hash_positions(self, item: str):
        positions = []
        for i in range(self.num_hashes):
            digest = hashlib.md5(f"{item}:{i}".encode()).hexdigest()
            pos = int(digest, 16) % self.size
            positions.append(pos)
        return positions

    def add(self, item: str) -> None:
        for pos in self._hash_positions(item):
            self.bits[pos] = 1

    def contains(self, item: str) -> bool:
        return all(self.bits[pos] for pos in self._hash_positions(item))


# Example usage
bf = BloomFilter(size=10_000, num_hashes=7)
for word in ["apple", "banana", "cherry", "date"]:
    bf.add(word)

print(bf.contains("apple"))   # True  (definitely inserted)
print(bf.contains("grape"))   # False (definitely not inserted)
print(bf.contains("fig"))     # False (probably not inserted)

This implementation uses MD5 with a seed suffix as a simple stand-in for independent hash functions. Production implementations typically use MurmurHash3 or xxHash for speed, or the double-hashing trick (computing two independent hashes and deriving k positions via linear combination) to avoid the cost of k separate hash computations.

Where Bloom Filters Are Used

When NOT to Use a Bloom Filter

Bloom filters are the wrong tool when you need exact membership answers, need to delete elements, need to store or retrieve the elements themselves, or need the false positive rate to be zero. They are also a poor fit when the set is small enough to fit in a hash set without memory pressure — the extra complexity is not worth it. Use a Bloom filter when you have millions of elements, a fixed memory budget, and can tolerate a small, controlled probability of false positives.

Related: Immutability in Practice: Why Unchangeable Data Makes Code Simpler — WierdX · Regular Expressions Explained — WierdX