Bloom Filters: Tiny Bit Arrays That Reliably Rule Out Matches

Bloom filters answer one question with absolute certainty: is something not in a set? They use a tiny bit array and a few hash functions to say “definitely not present” or “probably present,” trading a small chance of false positives for huge memory savings. This article explains how they work, how to size them, and where they shine.

Formula

The optimal number of bits m for a Bloom filter with n items and a desired false positive probability p is:

m = −n · ln(p) / (ln(2))²

The optimal number of hash functions k is:

k = (m / n) · ln(2)

Where:

• n = number of items you plan to insert
• p = acceptable false positive rate (e.g., 0.01 = 1%)
• m = number of bits in the array
• k = number of hash functions

The formula assumes independent, uniformly distributed hash functions. In practice, double hashing or a single 128-bit hash split into two 64-bit halves approximates this well.

Worked Example

Suppose you expect 1,000 items and want a 1% false positive rate. Using the defaults from the calculator:

1. Calculate m = −1000 · ln(0.01) / (ln(2))² ≈ −1000 · (−4.60517) / 0.48045 ≈ 9585 bits.
2. That is about 9585 / 8 ≈ 1198 bytes, or roughly 1.2 KB.
3. Calculate k = (9585 / 1000) · 0.693 ≈ 6.64, round to 7 hash functions.

The calculator rounds m to 9586 bits and k to 7, giving an array of 1199 bytes. With 7 hash functions and 9586 bits, the actual false positive rate is about 0.0081, slightly better than requested because of rounding.

How a Bloom Filter Works

A Bloom filter starts as an array of m bits, all set to 0. To add an item, you feed it to k hash functions, each producing an index between 0 and m−1, and set those bits to 1. To check membership, you compute the same k indices. If any bit is 0, the item is definitely not in the set. If all bits are 1, the item might be in the set—but could also be a false positive caused by collisions.

There is no deletion. Once a bit is set to 1, you cannot clear it without risking removing other items that share that bit. Variants like counting Bloom filters allow deletion by storing counters instead of single bits, at the cost of extra memory.

Choosing the Right Size

The golden rule: decide the false positive rate p and the number of items n first, then compute m and k. Common choices:

• 1% false positive rate: about 9.6 bits per item, 7 hash functions.
• 0.1% false positive rate: about 14.4 bits per item, 10 hash functions.
• 0.01% false positive rate: about 19.2 bits per item, 13 hash functions.

Each additional bit per item roughly halves the false positive rate, but the returns diminish. At 1% false positive, a Bloom filter uses about 1.2 KB for 1,000 items, compared to a hash set of 1,000 32-bit integers using 4 KB plus overhead. The savings grow with larger sets.

Common Problems and Misconceptions

False positives are not errors. They are a design trade-off. A false positive just means the filter says “maybe” when the item is not present; the system then performs a slower, authoritative check (like a database lookup).

False negatives are impossible. If the filter says “no,” the item is guaranteed absent. This is the core guarantee that makes Bloom filters useful.

More hash functions are not always better. Too many hash functions set more bits to 1 quickly, increasing the false positive rate. The optimal k is given by the formula; using more or fewer worsens performance.

Deletion is not supported. You cannot remove items without rebuilding the filter or using a counting variant.

Real-World Applications

Bloom filters appear in databases, caches, and network systems. For example:

• Databases: Apache Cassandra and PostgreSQL use Bloom filters to avoid disk lookups for non-existent rows.
• Caches: A Bloom filter can quickly check if a key is likely in a cache before querying the underlying store.
• Web crawlers: To avoid re-crawling URLs, crawlers use Bloom filters to track visited URLs.
• Networking: Routers use Bloom filters for packet classification and to share information about which packets have been seen.

In each case, the filter sits in front of a more expensive lookup. If the filter says “no,” the system skips the expensive operation entirely.

Alternatives to Bloom Filters

When you need to delete items, consider a counting Bloom filter (stores counters) or a cuckoo filter (supports deletion and has a lower false positive rate for the same memory, but is more complex). For exact membership with small sets, a simple hash set or sorted array may be faster. If you need to know which items are present, use a hash table. Bloom filters are best when memory is tight and false positives are tolerable.

Frequently Asked Questions

Can a Bloom filter give a false negative? No. If a bit is 0, the item was never inserted. False negatives are impossible by construction.

What happens if I insert more items than planned? The false positive rate increases. The formula assumes a fixed n; exceeding it degrades accuracy. You can rebuild the filter with a larger size.

How do I choose the number of hash functions? Use the optimal k = (m/n) · ln(2). For practical purposes, round to the nearest integer. Using more or fewer increases the false positive rate.

Can I remove items from a Bloom filter? Standard Bloom filters do not support deletion. Counting Bloom filters use counters to allow removal, but they consume more memory.

What is a good false positive rate for a cache? It depends on the cost of a false positive. If a false positive leads to a slow disk read, a rate of 0.1% or lower is common. For in-memory caches, 1% is often acceptable.

How much memory does a Bloom filter save? For 1 million items at 1% false positive, you need about 1.2 MB. A hash set of 1 million 32-bit integers would use at least 4 MB, plus overhead. The savings grow with the number of items.

Related

• Social Media Management: Scope & Getting Started
• UK Game Emulation: ROM & TPM Rules Explained
• Cheap QLED TV: What to Check Before Buying

in n | Number of items | items | 1000 | 1 | 1000000000
in p | False positive rate | fraction | 0.01 | 0.0000001 | 0.9999999
out m | Bit array size | bits | ceil(-n * ln(p) / (ln(2)^2)) | 0
out k | Hash functions | - | round((m / n) * ln(2)) | 0
out bytes | Array size in bytes | bytes | ceil(m / 8) | 0