Bloom filter
A Bloom filter is an array of m bits, all zero to begin with, and k independent hash functions. To insert an item you set the k bits its k hashes point at. To ask whether an item is present you read those same k bits: if any one of them is zero the item is definitely not in the set, because inserting it would have set that bit; if all k are one the item is probably in the set, but those bits may have been set by other items between them. The structure never stores the items themselves, which is why it fits in a few bits each.
When it is the right choice
Whenever a cheap, compact "almost certainly not here, do not bother looking" is worth more than an exact answer — a database skipping a disk read for a key that is not in a block, a browser checking a URL against a list of known-bad ones, a cache avoiding a network round trip. The filter is a front door, and whatever it lets through is checked properly behind it.
How it works
- Start with m bits, all zero, and pick k independent hash functions.
- To insert an item, compute its k hashes, reduce each one modulo m, and set those k bits to 1.
- To query an item, compute the same k positions and read the bits there.
- Any zero means the item is definitely not in the set. All ones means it is probably in the set.
Worth noticing
- There are no false negatives, ever, and that is a theorem rather than a tendency: inserting only ever turns a bit from 0 to 1, so a bit an item set is still set when that item is queried.
- A false positive is not a malfunction — it is several other items happening to have set exactly the bits this one reads. Watch for the frames where an insertion lands on a bit that is already set; those are the collisions a later false positive is made of.
- The filter cannot list what it holds, and cannot remove anything. Clearing an item’s bits would clear bits other items depend on, which is what the counting variant exists to fix.
Cost
- Best
- O(1)
- Average
- O(k)
- Worst
- O(k)
- Space
- O(m) bits