ABC Tools

Bloom Filters, Explained

After reading this you will be able to size a Bloom filter for any target error rate, predict its false positive rate from three numbers, and know exactly when the "definitely not present" answer is safe to trust.

What a Bloom filter is

A Bloom filter is a fixed array of m bits, all starting at 0, plus k hash functions. To add an item, you hash it k ways, map each hash to a bit position in [0, m), and set those bits to 1. To ask whether an item is present, you hash it the same k ways and check those bits. If any one of them is 0, the item was never added. If all k are 1, the item is probably present.

That asymmetry is the whole point. A Bloom filter never misses a real member (no false negatives), but it sometimes claims a non-member is present (false positives) because other items happened to set all the same bits. You trade a small, tunable error probability for a huge memory saving: roughly 10 bits per item instead of storing the items themselves.

Here is the hook. Store 1 million URLs in a set of 32-character strings and you use about 32 MB. Store them in a Bloom filter tuned to a 1% false positive rate and you use about 1.2 MB, a 27x reduction, while every "not in the set" answer stays exact.

When to use one, and when not

Reach for a Bloom filter when a "no" answer lets you skip expensive work, and a rare wrong "yes" only costs you a wasted check. Databases like Cassandra and HBase put a Bloom filter in front of each on-disk table so a lookup for a missing key avoids a disk read. Web crawlers use them to skip URLs already seen. CDNs use them to decide whether an object is worth caching after one hit.

Avoid a Bloom filter when a false positive is dangerous rather than merely wasteful, when you need to delete items (see below), or when you need to enumerate what is stored. The filter holds no items, only bits, so you cannot read anything back out. If you need order, iteration, or exact membership, use a real set or hash table. The Data Structure Visualizer shows how ordinary hash tables and tries handle those jobs.

A Bloom filter answers "possibly present" for items you never added. Never use one where a false positive causes an unrecoverable action, such as skipping a security check or approving a transaction. The safe pattern is: treat "no" as final, treat "yes" as "go verify".

The false positive formula and where it comes from

Insert n items into m bits using k hash functions. Assume each hash lands uniformly at random. Each of the k \cdot n bit-settings picks one position, so the chance that a specific bit stays 0 is:

P(\text{bit} = 0) = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}

Here m is the array size in bits, n the number of inserted items, and k the number of hash functions. The approximation uses (1 - 1/m)^m \approx e^{-1} for large m. A false positive needs all k probed bits to already be 1, and the chance a bit is 1 is 1 - e^{-kn/m}, so:

p \approx \left(1 - e^{-kn/m}\right)^k

This is exactly the theoretical rate the playground plots. The one assumption that can bite you is independence: real hash functions are not perfectly uniform, so measured rates drift a little from theory. That is why the tool also queries thousands of random never-added strings and reports an empirical rate next to the formula.

Choosing m and k

Given the number of items n and a target false positive rate p, two formulas give the optimal sizing. Minimize m first:

m = -\frac{n \ln p}{(\ln 2)^2}

Then the number of hashes that minimizes error at that size is:

k = \frac{m}{n} \ln 2

The intuition for k = (m/n)\ln 2: too few hashes and each item sets too few bits to be distinctive; too many and you flood the array with 1s. The sweet spot fills exactly half the bits. When about 50% of bits are 1, each probe is a coin flip, and k independent coin flips give the smallest product.

For p = 0.01 the numbers come out to about 9.6 bits and 6.9 hashes per item, which you round to 10 bits and 7 hashes. Every factor of 10 you shave off p costs about 4.8 more bits per item, because -\ln p / (\ln 2)^2 grows linearly in the number of nines.

With m = 1000 bits and k = 7 hashes, the false positive rate climbs as you add items: about 0.00008 at 50 items, 0.0094 at 100 items, 0.077 at 150 items, and 0.22 at 200 items. Fewer hashes lower the rate at high load but raise it at low load.

A worked example you can reproduce

The playground's demo button loads its field defaults. Work the sizing math by hand so the recommended numbers are not a mystery.

Sizing for 1000 items at 1% error

  1. Start with n = 1000 and p = 0.01.
  2. Compute \ln p = \ln 0.01 = -4.605 and (\ln 2)^2 = 0.4805.
  3. Bits: m = -\frac{1000 \times (-4.605)}{0.4805} = 9585, so round up to about 9586 bits (roughly 1.2 KB).
  4. Hashes: k = \frac{9585}{1000} \times 0.6931 = 6.64, round to 7.
  5. Check the achieved rate with k = 7: fill fraction is 1 - e^{-7 \times 1000 / 9585} = 0.517, and p = 0.517^7 = 0.0098, just under 1%.

The fill fraction of 0.517 confirms the half-full rule: at optimal k, about half the bits end up set.

The curve below shows how the false positive rate for this filter (m = 9586, k = 7) rises as you insert more than the planned 1000 items. Overfilling is the single most common cause of a Bloom filter that "stopped working".

At the design point of 1000 items the rate is about 1%. Insert 2000 items instead and it climbs to about 8%, an eightfold increase for double the load.

Reading the results in the playground

Two numbers sit side by side: the theoretical rate from the formula and the empirical rate from querying random strings. Expect them to agree within sampling noise. If you query 10,000 random strings against a filter with a true rate of 1%, you expect about 100 false positives, with a standard deviation of \sqrt{10000 \times 0.01 \times 0.99} \approx 9.9. So an observed count anywhere from about 80 to 120 is normal. A large, persistent gap points at a weak hash or a bug, not at bad luck.

Watching the bits light up teaches the double-hashing trick the tool uses. Rather than compute 7 independent hashes, it computes two FNV-1a hashes h_1 and h_2, then derives the rest as g_i = (h_1 + i \cdot h_2) \bmod m for i = 0, 1, \dots, k-1. This produces k well-spread positions from two real hashes, and the measured error stays close to theory.

If the empirical rate sits far above theory, check whether two of your k positions collide. With small m and large k, h_1 + i \cdot h_2 can repeat a cell, which sets fewer than k distinct bits per item and inflates errors. Larger m makes collisions rare.

Common mistakes

Trying to delete an item
Clearing the k bits of one item may clear a bit another item relies on, creating a false negative. A plain Bloom filter cannot delete. Use a counting Bloom filter, which stores a small counter per cell instead of one bit, at roughly 4x the memory.
Underestimating n
The rate is fixed by kn/m. Double n without changing m and the fill jumps; the demo chart shows 1% becoming 8% at 2x load. Size for your peak count, not your average.
Reusing one hash and slicing it
Splitting a single 64-bit hash into k chunks correlates the positions and skews the error. Double hashing with two independent bases is the tested compromise.
Treating "possibly present" as "present"
Always follow a positive with the authoritative check. The filter's job is to eliminate the easy "no", not to replace the source of truth.

Related tools

Bloom filters sit next to several other structures worth exploring. The Consistent Hashing Ring shows another use of hashing to partition data, where adding a server moves only 1/N of the keys. The Cache Replacement Simulator pairs naturally with filters, since both decide what to keep and what to skip. If your interest is the hashing math itself, the IEEE-754 Floating Point Explorer shows how bit patterns encode numbers, and the Tail Latency & Autoscaling Simulator shows what happens when the disk reads a Bloom filter is meant to avoid start piling up under load.

Frequently asked questions

Can a Bloom filter give a false negative?

No. If an item was added, all k of its bits were set to 1 and stay 1 (you never clear bits). So a "definitely not present" answer is always correct. Only "possibly present" can be wrong.

How much memory does one item cost?

About -\ln p / (\ln 2)^2 bits, independent of the item's size. That is 9.6 bits at 1% error, 14.4 bits at 0.1%, and 19.2 bits at 0.01%. Each extra nine adds about 4.8 bits.

What is the best number of hash functions?

k = (m/n)\ln 2, rounded to the nearest integer. This fills about half the array with 1s. Using more hashes than this makes the error worse, not better, because the bits fill up faster than the extra probes help.

Why do the theoretical and empirical rates differ slightly?

The theory assumes perfectly uniform, independent hashing. Real hashes and double hashing are close but not exact, and the empirical rate is a sample. With 10,000 queries at a true 1% rate, expect the count to vary by about 10 either side of 100 just from randomness.

What is a counting Bloom filter?

A variant that replaces each bit with a small counter (often 4 bits). Adding increments the k counters, deleting decrements them, and the item is "present" if all k counters are above zero. It supports deletion at roughly 4x the memory of a plain filter.

Try it yourself in the tool

Related tools

Cache Replacement Simulator

Animate FIFO, LRU, LFU, CLOCK, ARC and Bélády's OPT on any access sequence.

Consistent Hashing Ring

See why adding a server moves 1/N of the keys, not all of them.

Data Structure Visualizer

Watch BST, AVL, red-black trees, heaps, hash tables, tries and union-find work, step by step.

Digital Logic Gate Simulator

Build circuits from gates and flip-flops, wire them up, and watch the signals flow live.

Git Branching Sandbox

Type git commands and watch the commit DAG, branches and HEAD move — with levels, remotes, undo, and merge-vs-rebase contrast.

IEEE-754 Floating Point Explorer

Flip the bits of a float and see why 0.1 + 0.2 ≠ 0.3.