Bloom Filter

A bit array of size m, plus k hash functions. Answers "is this item possibly in the set?" using a fraction of the memory a real set would need, at the cost of occasional false positives.

How it works

add(item) hashes the item k times (here via the Kirsch-Mitzenmacher trick: deriving k hashes from just 2 base hashes, hi = h1 + i·h2, which is what most real implementations do) and sets each resulting bit to 1.

has(item) hashes the item the same way and checks whether all k bits are already set. If even one bit is 0, the item was definitely never added: a Bloom filter never produces false negatives. If all k bits are set, the item is probably present, but another combination of items could have coincidentally set the same bits, producing a false positive.

More bits (m) or fewer hash functions (k) relative to the number of items inserted lowers the false-positive rate, at the cost of more memory. Try cranking up the item count below and watch the fill ratio (and false-positive rate) climb.

Interactive demo

Suggested k for current m and 0 item(s): 44
Items added0
Fill ratio0.0%
Est. false-positive rate0.00%
Bits used64 bits (8 B)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new BloomFilter(m, k)Allocate an m-bit array with k hash functions.O(m) space
add(item): voidSet the k bits derived from item.O(k) time
has(item): booleanTrue if all k derived bits are set ("maybe"); false means "definitely not".O(k) time
optimalM(n, p): numberBits needed for n items at false-positive rate p.O(1)
optimalK(m, n): numberBest hash-function count for m bits and n items.O(1)

References

Original papers

Library implementations

Real-world use cases