Bloom Filters

In plain words

"Have I seen this before?" A crawler asks it forty times per page, a database asks it before opening a file on disk, a cache asks it before storing something new. Answering exactly means keeping the whole set — every key, somewhere, looked up every time. A Bloom filter answers from a small block of memory, in nanoseconds, with one concession: it can be wrong in one direction only.

How it works

The filter is an array of bits, all zero. Pick k hash functions.

1. Add an item

   Hash it k times. Each hash gives a position; set that bit to 1.

2. Ask about an item

   Hash it the same k times and look at those bits. If any is 0, the item was never added — certain. If all are 1, it was probably added.

3. Where the 'probably' comes from

   Those bits might all have been set by other items. That is a false positive. The fuller the array, the likelier it is.

import hashlib, math

class BloomFilter:
    def __init__(self, n_items: int, fp_rate: float = 0.01):
        # Size the array for the expected count and the error you accept.
        self.m = math.ceil(-n_items * math.log(fp_rate) / (math.log(2) ** 2))  # bits
        self.k = max(1, round(self.m / n_items * math.log(2)))                  # hashes
        self.bits = bytearray(self.m // 8 + 1)

    def _positions(self, item: str):
        # Two real hashes combined k ways — the standard trick.
        h1 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.sha1(item.encode()).hexdigest(), 16)
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item: str):
        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] & (1 << (p % 8)) for p in self._positions(item))

seen = BloomFilter(n_items=, fp_rate=0.01)   # ≈ 1.2 GB, k = 7

Sizing it

The false-positive rate depends on how full the array is. With m bits, n items and k hashes it is roughly (1 − e^(−kn/m))^k. The widget lets you move m and k and watch it. Two things fall out:

per item, for 1% false positives

~10 bits

hashes at 10 bits per item

k ≈ 7

for a billion URLs (vs ~60 GB exact)

1.2 GB

false negatives, ever

0 %

There is a best k for any bits-per-item: more hashes fill the array faster, fewer leave more collisions unnoticed. The constructor above computes it.

Where it is used

The pattern is always the same: put the filter in front of something expensive, and let it say no.

In every case a false positive is cheap — one wasted lookup, one skipped page, one unnecessary cache fill. A false negative would be expensive, and the filter never produces one.

Where it goes wrong

• Deletion. You cannot clear a bit; other items may share it. Use a counting filter (a small counter per position instead of a bit) or rebuild the filter periodically.
• Growth. A filter sized for a million items is useless at ten million: the false-positive rate climbs toward 100%. Size for the final count, or use a scalable variant that adds a new filter as the old one fills.
• Bad hashes. Correlated hash functions collide together and the maths stops applying. Two good hashes and k combinations of them (as in the code) is the standard trick.
• When you needed certainty. A filter is for "skip the work if you can". It is not a set, and "probably" is not an answer you can bill on.

Take this with you

• The one idea: a tiny structure that can say "definitely not" for certain and "probably yes" cheaply, in front of something expensive.
• In an interview, give the numbers — about ten bits per item for 1% false positives — and say which direction it can be wrong in.
• At work, you are probably already using one: inside your database, your CDN, or your browser's safe-browsing check. Reach for it when "skip the work if you can" is the shape of the problem.