Bloom Filter
A probabilistic set: k hash functions set k bits. False positives possible, false negatives impossible.
Bloom Filter: Four words in, one stranger looks like a member
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.