Tool · 2026-06-24
Bloom filter, 64 bits, three hashes.
A Bloom filter is a fixed-size bit array plus a handful of hash functions. Add an item, write it three times into the array at three hashed positions. Ask if an item is present, read those same three positions: if any is zero the answer is no, if all three are one the answer is probably. It never says no when it should say yes; it sometimes says yes when it should say no. The price of that asymmetry is the whole point.
Bit array · 64 cells
Add a word
Check membership
- Items added (n)
- 0
- Bits set
- 0 of 64
- False-positive odds
- 0%
How the bits get picked
Three hash functions sit between your word and the bit array. Each one walks the characters of the word and folds them into a 32-bit integer, then takes the result modulo 64 to pick a bit. The three hashes differ only in their starting constant — same algorithm, different seeds, different bit. This page uses FNV-1a, a small non-cryptographic hash that fits in five lines: xor the next byte into the accumulator, multiply by the FNV prime, mask to 32 bits, repeat.
Why it can lie
Two unrelated words can share a hash. With three hashes per word and 64 bits to land on, collisions are inevitable as the filter fills. Once every bit you'd hash a query to has already been set by some earlier word, the filter says yes to a query that was never added. It cannot say no by mistake, because removing an item would mean clearing bits that other items also rely on. That is also why a Bloom filter has no delete: once a bit goes up it stays up.
The formula
After n insertions into a filter with m bits and k hashes, a given bit is still zero with probability (1 − 1/m)^(kn). The chance a query for an unseen item hits k bits that are all set is that same expression flipped and raised to k: (1 − (1 − 1/m)^(kn))^k. The number under "false-positive odds" above is exactly that. With 64 bits and three hashes the filter degrades fast — by ten items the odds are already past ten percent. Real filters use thousands of bits, often gigabytes of them.