# Bloom Filters: Probably Present, Definitely Useful

> A Bloom filter answers 'have I seen this before?' using a fraction of the memory a real set would need — by allowing one specific kind of wrong answer. It's the data structure behind databases skipping disk reads they don't need.

URL: https://harshith.in/blog/bloom-filters/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, databases

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.