Bloom filter: an interactive false positive simulator

A Bloom filter is a bit array that answers “have I seen this before?” with either “definitely not” or “probably yes”. Adding an item sets k bits chosen by k hash functions; checking it looks at the same k bits. It never says no to something it has seen, it sometimes says yes to something it has not, and at about 10 bits per item that false positive rate is 1%.

The playground is a 64-bit filter with three hash functions. Add some animals, then check colours you never added, and keep going until a colour comes back “probably yes”.

How a Bloom filter works

1. Start with m bits, all 0, and pick k hash functions that each map an item to a bit.
2. To add an item, hash it k times and set those k bits to 1. A bit already at 1 stays 1.
3. To check an item, hash it the same k times. If any of those bits is 0, the item was never added: definitely not.
4. If all k bits are 1, the item was probably added, or other items happened to set every one of its bits: a false positive.

The filter stores no items, only bits, which is why it is so small and why it cannot list what it holds or remove anything: clearing a bit could clear it for another item too.

Bloom filter false positive rate

After n items, the chance that a given bit is still 0 is about e^−kn/m, so the false positive rate is about (1 − e^−kn/m)^k. More precisely, it is the share of bits set, to the power k: an item never added has to land on k set bits by chance. The playground shows both the measured rate and the formula; on a small filter they differ by however much the actual words collided.

How big a Bloom filter should be

For n items and a target false positive rate p, use m = −n ln p / (ln 2)² bits and k = (m / n) ln 2 hash functions. Each halving of p costs a constant extra 1.44 bits per item.

Compare a hash set of the same million items: storing even 40-byte URLs is 40 MB before any overhead. The Bloom filter is 30 times smaller at 1% and does not grow with the size of the items.

Bloom filter vs hash set

A hash set is exact and can list and delete what it holds, but it stores every item. A Bloom filter stores a few bits per item regardless of item size, and pays for that with false positives and no deletes. Use a Bloom filter in front of something expensive, where a false “probably yes” only costs an extra lookup and a “definitely not” saves one.

Where Bloom filters are used

To delete, use a counting Bloom filter (a small counter per position instead of a bit) or a cuckoo filter. To grow without knowing n in advance, chain filters of increasing size (a scalable Bloom filter).

A Bloom filter in code

import hashlib, math

class BloomFilter:
    def __init__(self, n: int, p: float):
        self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)   # bits
        self.k = max(1, round(self.m / n * math.log(2)))          # hash functions
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        d = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]   # k hashes from two

    def add(self, item: str) -> None:
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def might_contain(self, item: str) -> bool:
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(item))

seen = BloomFilter(n=1_000_000, p=0.01)   # 9,585,059 bits (1.2 MB), k = 7

Two good hashes are enough: the k positions come from h1 + i × h2, which is as good as k independent hash functions in practice. In Redis, the RedisBloom module gives you BF.ADD and BF.EXISTS without writing any of this.

In a system design interview

Reach for it when the question is “have we seen this?” at a scale where storing everything is expensive, and say the numbers: “A Bloom filter in front of the URL store: a billion URLs at 1% false positives is about 1.2 GB with 7 hash functions, so it fits in memory, and a false positive only costs one extra lookup.” Expect the follow-ups: deletes (counting filter), what a false positive costs the user, and how the filter is rebuilt or grown as the set grows.

Watch a strong candidate design a web crawler, or read the Bloom filters guide for the maths and the variants.

Questions people ask