AlgoScope

Bloom Filter

A probabilistic set: k hash functions set k bits. False positives possible, false negatives impossible.

Data structures, data structure, advanced
cat: probably present.10111203140516070809110111112113014015

Bloom Filter: Four words in, one stranger looks like a member

Decision, step 6 of 10

Query "cat": hashes 6, 4, 0. All three bits are 1, so the answer is "probably", and here it happens to be right: "cat" was inserted.

Cost

Insert
O(k)
Query
O(k)
Space
O(m bits)

False-positive rate depends on m n and k.