You want to know if a key has been seen before, but storing every key costs more memory than you have. A Bloom filter answers the membership question in a tiny fixed-size bit array — at the price of occasionally saying “yes” when the true answer is “no.” That one-sided error turns out to be exactly the trade real systems want.

A Bit Array and a Few Hashes

A Bloom filter is an array of bits, all zero to start, plus k independent hash functions. To add an element, hash it k ways and set those k bits:

text
   add("cat"):  h1→3  h2→7  h3→11
   bits: [0 0 0 1 0 0 0 1 0 0 0 1 0 0]
              3       7       11

To check membership, hash the same way and look at those bits:

text
   check("cat"): bits 3,7,11 all set?  → "probably present"
   check("dog"): any of its bits 0?    → "definitely absent"

If any required bit is 0, the element was never added — a guaranteed answer. If all are 1, it’s probably present.

The Asymmetry That Makes It Useful

This is the key property:

text
   "definitely not in the set"   ← always correct (no false negatives)
   "probably in the set"         ← may be wrong   (false positives possible)

A false positive happens when other elements collectively set all of a missing element’s bits. You never get a false negative — if it was added, its bits are set. So a Bloom filter never misses something it has seen; it only occasionally imagines something it hasn’t.

Tuning the Error

The false-positive rate is governed by the array size m, the number of elements n, and the hash count k. More bits per element → fewer false positives:

text
   ~10 bits per element, optimal k  →  ~1% false positives
   add more bits                    →  exponentially fewer

You pick the rate you can tolerate and size the array accordingly. Note: you can’t delete from a basic Bloom filter — clearing a bit might unset one shared with another element (a counting Bloom filter solves this).

Where They Earn Their Keep

The classic use is skipping expensive work. An LSM-tree database keeps a Bloom filter per on-disk SSTable. Before reading a file from disk to look for a key, it checks the filter:

text
   lookup(key):
     for each SSTable:
       filter says "absent"?  → skip the file entirely (no disk read)
       filter says "present"? → read it and check for real

A 1% false-positive rate means 99% of pointless disk reads are avoided for a few bits per key. The same pattern shows up in caches (“is this worth a lookup?”), CDNs, and spell-checkers.

Takeaways

  • A Bloom filter stores set membership in a bit array using k hash functions — far smaller than holding the elements themselves.
  • It never returns a false negative but can return a false positive: “definitely not” is exact, “probably yes” is not.
  • Size and hash count trade memory for a lower false-positive rate; basic versions can’t delete.
  • They shine as a cheap pre-check to avoid expensive work — like an LSM-tree skipping disk reads for absent keys.