Bloom Filter: Probabilistic Set Membership

Bit Array

Array size m 128

Hash functions k 4

Insert / Query

Type a word and press Query.

Live Stats

Items inserted (n)

Bits set / m

0 / 128

Theoretical FP rate

0.0%

Measured FP rate

—

How it works

A Bloom filter is a space-efficient probabilistic structure for set membership. It holds an m-bit array (all zero at start) and k independent hash functions h₁…h_k, each mapping any item to a position in [0, m).

Insert(x):  for i in 1..k:  A[hᵢ(x)] = 1
Query(x):   "possibly in set" if A[hᵢ(x)] = 1 for ALL i
            "definitely NOT in set" if any A[hᵢ(x)] = 0

The filter never produces a false negative — if an item was inserted, every one of its bits is guaranteed set. But it can produce a false positive: another item's hashes might all happen to land on bits that were set by other insertions. After inserting n items, the expected false-positive probability is:

p ≈ (1 − e^(−kn/m))^k

optimal k for a given m/n:  k* = (m/n)·ln 2 ≈ 0.693·(m/n)

This simulator uses k independent FNV-1a-style hashes (one seed per function) on whatever word you type. Each ring position is one bit; lit (orange) spheres are set bits. The "run trials" button queries hundreds of random words that were never inserted and measures how many are wrongly reported present — that measured rate should track the theoretical curve above as you change m, k, and n.

Real-world use: Bloom filters back Chrome's Safe Browsing list, Cassandra/HBase/LevelDB "does this key exist on disk" checks, CDN cache-miss filtering, and Bitcoin SPV wallets — anywhere a cheap "definitely not present" answer can skip an expensive lookup.

Bit = 0 Bit = 1 (set)

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.