Home▸Distributed & Parallel Computing▸Bloom Filter — Probabilistic Set Membership

🌸 Bloom Filter — Probabilistic Set Membership

Add items to a bit array via k hash functions and test membership. Bloom filters never false-negative but can false-positive — tune bit-array size and hash count and watch the false-positive rate.

Distributed & Parallel Computing3DModerate60 FPS

About Bloom Filter

A Bloom filter is a probabilistic data structure that answers membership queries in O(1) time and O(m) space, where m is the bit-array size — far smaller than storing the items themselves. When you insert an element, k independent hash functions map it to k positions in an m-bit array and set those bits to 1. To test membership, the same k positions are checked: if any is 0 the element is definitely absent; if all are 1 it is probably present. Bits are never cleared, so false negatives are impossible, but hash collisions can produce false positives whose probability is approximated by (1 − e^(−kn/m))^k, where n is the number of inserted items.

This simulator lets you type words and add them to a live bit-array visualisation, query membership to see false positives appear as the array fills, and adjust the array size m and hash count k via sliders. The theoretical false-positive rate and measured rate over 2,000 random test queries update in real time, making the trade-off between space and accuracy immediately visible.

Frequently Asked Questions

Why can a Bloom filter never produce a false negative?

When an element is inserted, all k of its hashed bit positions are set to 1 and are never cleared. Therefore, if you test an element that was genuinely inserted, all k bits will be 1 and the filter will correctly report "possibly in set". A false negative would require a bit to flip back to 0, which never happens.

What is the formula for the false-positive probability?

After inserting n items into an m-bit array with k hash functions, the fraction of bits still 0 is approximately e^(-kn/m), so the probability that all k positions for a non-member are 1 is (1 - e^(-kn/m))^k. For example, with m = 64, k = 3, and n = 10 items, the false-positive rate is roughly 5%.

How do you choose the optimal number of hash functions k?

The value k = (m/n) x ln 2 minimises the false-positive rate for a given m and n. Too few hashes leave many bits unset and reduce discrimination; too many hashes fill the array quickly and increase collisions. For a 1% target error rate, the optimal array size is roughly 9.6 bits per inserted item.

Why can't you delete items from a standard Bloom filter?

Deleting an item would require clearing its k bit positions, but those bits may also have been set by other inserted items, so clearing them would silently introduce false negatives for those items. A Counting Bloom filter replaces each bit with a small counter, incremented on insert and decremented on delete, to support safe deletion at the cost of extra memory.

⚙ Under the hood

A Bloom filter tests set membership with k hash functions over a bit array: no false negatives, tunable false positives. Watch bits light up and the error rate track (1−e^(−kn/m))^k.

Bloom filterhashingfalse positiveprobabilisticCanvas 2D

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install