Toolgeist › Developer

Bloom Filter Playground — Real Bit Array, Live False-Positive Rate

A real Bloom filter backed by an actual bit array, with each item hashed to k positions using two real hash functions combined via the Kirsch-Mitzenmacher technique. It gives one hard guarantee — an inserted item always tests as present, zero false negatives, ever — and one probability: the false-positive rate, measured live here against 300 real membership tests on items never inserted, compared directly to the standard theoretical formula rather than just stated.

How to use Bloom Filter Playground

  1. Click words to insert them into the filter.
  2. Watch the bit array fill up.
  3. Test any word for membership.
  4. Compare the live empirical false-positive rate to the theoretical formula, and shrink the bit array to watch it climb.

Frequently asked questions

Why can a Bloom filter have false positives but never false negatives?
Inserting an item sets all k of its hash-derived bits, so testing that same item later always finds every one of its bits set — a guaranteed true positive. But other items can coincidentally set the exact same bits through hash collisions, which is exactly what occasionally makes an unrelated item test as "possibly present" even though it was never inserted.
What determines the false-positive rate?
The ratio of bit array size to number of inserted items, and the number of hash functions — captured in the formula (1 − e^(−kn/m))^k, which the live empirical rate here is measured against directly rather than just quoted.
Where are Bloom filters actually used?
Databases (checking if a key might exist before an expensive disk read), web browsers (Chrome's old Safe Browsing malicious-URL check), and distributed systems (Cassandra uses one per SSTable to skip files that definitely do not contain a queried key).
Why use k derived hash functions instead of k truly independent ones?
The Kirsch-Mitzenmacher technique combines just two real hash functions into k effective ones (h_i = h1 + i·h2) and is provably about as good as k independent hashes for this purpose, while only needing to compute two real hashes per item instead of k.

Related Developer tools

Also searched for: bloom filter simulator online · false positive rate calculator bloom filter · bloom filter demo interactive

Browse all 738 free tools on Toolgeist →