Skip to main content
Be Bitwise

Bloom Filters

Bloom Filters & Probabilistic Data Structures · Data & Hashing track

6 min read

In this module

The Art of Almost Certain

You're running a web service that blocks malicious URLs. The blocklist holds 10 million known-bad domains. Every incoming request needs the same answer: is this URL on the list? A hash set works, sure — and chews through hundreds of megabytes doing it. What if you could answer the same question in 10 megabytes, granting yourself a tiny margin for error?

A bloom filter is a probabilistic membership test: it tells you whether an element is definitely not in a set or possibly in it. The structure costs a fraction of the memory an exact data structure would, paid for in occasional false positives.

How It Works

A bloom filter has two moving parts:

  1. A bit array of m bits, every one of them starting at 0.
  2. A set of k independent hash functions, each mapping any input to one of the m bit positions.

Insertion: to add an element, run it through all k hash functions and flip every resulting bit to 1.

text
hash1("evil.com") % m = 3 --> set bit 3 to 1
hash2("evil.com") % m = 7 --> set bit 7 to 1
hash3("evil.com") % m = 1 --> set bit 1 to 1
Bit array: [0, 1, 0, 1, 0, 0, 0, 1, 0, 0]
0 1 2 3 4 5 6 7 8 9

Lookup: run the same k hashes on the query element and check whether every resulting bit is 1.

  • Any bit is 0 → the element is definitely not in the set. Inserting it would have set that bit.
  • All bits are 1 → the element is possibly in the set. Some unrelated elements may have lit up those same bits.
Key Concept

A bloom filter answers membership queries with zero false negatives and a tunable false positive rate. A "no" is final — the element is definitely absent. A "yes" is provisional, with a small probability of being wrong.

False Positives in Action

After inserting several URLs, the bit array has many bits set to 1:

text
Bit array: [1, 1, 0, 1, 1, 0, 1, 1, 0, 1]

Now we check "safe.com":

text
hash1("safe.com") % m = 1 --> bit 1 is 1
hash2("safe.com") % m = 4 --> bit 4 is 1
hash3("safe.com") % m = 7 --> bit 7 is 1

All three bits read 1, so the bloom filter answers "possibly in the set". Trouble is, "safe.com" was never inserted — those bits got flipped by completely unrelated URLs. That's a false positive in the wild.

Three knobs control the false positive rate:

  • m (bit array size): bigger is always better, until memory hurts.
  • k (number of hash functions): there's a sweet spot. Too few or too many, and the rate climbs.
  • n (elements inserted): each insertion sets a few more bits, raising the chance the next stranger walks into a fully-lit collision.

The optimal hash count works out to k = (m/n) · ln(2), and at that k the false positive rate sits around (1/2)^k.

The explorer below starts as the same 10-bit, three-hash filter, though its real hash functions put strings on different bits from the hand-drawn example above. Insert the sample words (the three domains from earlier), query safe.com and you'll get a firm no; then try docs.org, which nobody inserted, and watch it sneak through as a false positive. After that, drag m and k around and see how far the measured rate strays from the formula.

Bloom filter explorer

Type a string to see its 3 bit positions, insert it, then query strings you never inserted.

Each cell shows its bit and, below, its index. Blue is a set bit. Outlined cells are the current string's positions: green if the bit is 1, red if it's 0.

"safe.com": definitely not present (bits 0, 6, 2 are 0)

h1 = 0xf32f4e66, h2 = 0x3855718e. Positions (h1 + i·h2) mod 10 for i = 0..2: 0, 6, 2

Inserted, n
0
Bits set
0 of 10 (0%)
Expected fill, 1 − e^(−kn/m)
0%
Theory, (1 − e^(−kn/m))^k
0.0%
Measured on 1,000 strangers
0.0%
Optimal k = (m/n) · ln 2
needs n > 0

Strangers are the strings stranger-0 to stranger-999, none of them inserted. Theory assumes independent, uniform hashes, so tiny filters drift from it.

Which hash functions?

h1 is 32-bit FNV-1a and h2 is 32-bit DJB2, both over the string's UTF-8 bytes and both finished with MurmurHash3's fmix32 mixer so the low bits depend on every byte. The k positions come from double hashing (Kirsch and Mitzenmacher): position i is (h1 + i·h2) mod m. If h2 mod m is 0 the step becomes 1, otherwise all k positions would land on the same bit.

The program below builds the 10-bit, three-hash filter from this lesson, inserts three domains and queries four. Only "evil.com" was inserted: before you run it, guess which of the other three come back "possibly". The second half measures the false positive rate of a bigger filter against the formula.

Try itPredict each query's answer, then change m, k or n in part 2 and watch the false positive rate move.
C (GCC 9.2.0)

With seven of the ten bits lit, a stranger only escapes if one of its three positions hits a zero, so two out of three non-members get waved through. A hash can also land on the same bit twice, which is one reason tiny filters behave worse than the formula suggests.

Memory Savings

Ten million elements at a 1% false positive rate works out to about 9.6 bits per element, or roughly 12 MB total. The equivalent hash set lands somewhere in the hundreds of megabytes.

Push to a billion elements at the same 1% rate: the bloom filter needs around 1.2 GB. The hash set needs tens of gigabytes — and probably your manager's signature on a procurement order.

Limitations

No deletion. You can't remove an element from a standard bloom filter, because clearing those bits would simultaneously erase any other element that happens to share them. Counting bloom filters swap each bit for a small counter, which permits deletion at the cost of more memory.

No enumeration. A bloom filter never tells you what's inside. The only conversation it has is "is X in the set?" — yes or no.

False positives are baked in. You can drive the rate arbitrarily low, but it'll never reach zero. If your application can't tolerate any false positives, the bloom filter is the wrong tool.

Real-World Uses

Google Chrome historically used a bloom filter for Safe Browsing — checking each URL against the known-phishing list without dragging the whole list down to your laptop.

Databases (Cassandra, HBase, LevelDB) lean on bloom filters to skip useless disk reads. Before opening a file to look for a key, an in-memory filter answers "definitely not in there" for the vast majority of misses, saving an SSD seek every time.

CDN caches use bloom filters to decide what's worth caching. The first request adds a URL to the filter. The second request hits the filter, gets a "yes", and triggers actual caching. Cold one-shots pass through untouched.

Routers use bloom filters to track packets they've already seen, giving them duplicate detection with practically no memory overhead.

Why They Stick Around

Two big caveats — no deletion, no enumeration — sound disqualifying on paper. In practice, almost nobody who reaches for a bloom filter cares. The memory savings on membership queries at scale are so disproportionate that "approximate, read-only set membership" turns out to be a remarkably common shape of problem. That's how an idea Burton Bloom published in 1970 ended up inside Chrome, Cassandra, HBase, and the routing fabric of the modern internet.