🌸 Bloom Filter
Probabilistic set membership
No false negatives
Bits set: 0 / 64
Item
Parameters
Controls
Stats
Inserted n
0
Bits set
0 / 64
Theory FP
0.0%
Measured FP
—
Log
Info & Theory

A Bloom filter is a compact probabilistic structure that answers one question: "is this item in the set?" It uses an array of m bits and k hash functions, storing no items at all.

Adding an item

Hash the item with all k functions to get k positions in [0, m), then set those bits to 1. Bits are never cleared.

Querying an item

  • If any of the k bits is 0 → definitely not in the set.
  • If all k bits are 1 → possibly in the set.

Because set bits are never reset, a true member always passes — so there are no false negatives. But collisions can make a non-member look present: a false positive.

The error rate

After inserting n items, the probability a random non-member yields all-ones is approximately (1 − e^(−kn/m))^k. The term e^(−kn/m) estimates the share of bits still 0.

Tuning k and m

The error is minimised at k = (m/n)·ln 2, and a target rate p needs m = −n·ln p / (ln 2)² bits — about 9.6 bits per item for 1%.

About Bloom Filter

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

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.