What is a Bloom filter and what trade-off does it make?

Question

Accepted Answer

A **Bloom filter** is a space-efficient **probabilistic** structure that answers set membership with one twist: it can have **false positives** but **never false negatives**. "Definitely not present" is certain; "possibly present" needs a real check.

## How it works

A bit array of `m` bits and `k` hash functions. To **add** an item, set the `k` bits it hashes to. To **query**, check those `k` bits — if any is 0, the item is definitely absent.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Code

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| Operation | Time | Space |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

No false negatives; false-positive rate falls as `m` (and tuned `k`) grow.

## Trade-offs

- **Strengths:** tiny memory footprint vs storing full keys; constant-time ops.
- **Weaknesses:** false positives; **cannot delete** (a standard Bloom filter); cannot list members.

## Why it matters

Bloom filters cheaply skip expensive work: databases (e.g. Cassandra, HBase) use them to avoid disk reads for keys that **definitely** aren't on disk.

They embody a classic systems trade-off — accept a small, bounded error rate in exchange for a huge reduction in memory and I/O.