Wat is een Bloom filter en welke afweging maakt het?

Question

Accepted Answer

A **Bloom filter** is een ruimte-efficiënte **probabilistische** structuur die set-lidmaatschap beantwoordt met één twist: het kan **false positives** hebben maar **nooit false negatives**. "Zeker niet aanwezig" is zeker; "mogelijk aanwezig" vereist een echte controle.

## Hoe het werkt

Een bitarray van `m` bits en `k` hash-functies. Om een item toe te **voegen**, stelt u de `k` bits in waar het naar gehasht. Voor **query**, controleert u die `k` bits — als een van deze 0 is, is het item zeker afwezig.

```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)
```

| Bewerking | Tijd | Ruimte |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Geen false negatives; false-positive rate daalt naarmate `m` (en afgestemd `k`) groeien.

## Waarom het belangrijk is

- **Sterken:** piepklein geheugengebruik versus volledige sleutels opslaan; constant-time operaties.
- **Zwakten:** false positives; **kan niet verwijderen** (een standaard Bloom filter); kan leden niet opsommen.

## Waarom het belangrijk is

Bloom filters slaan goedkoop dure werk over: databases (bijv. Cassandra, HBase) gebruiken ze om schijflezen te vermijden voor sleutels die **zeker** niet op schijf staan.

Ze belichamen een klassieke systeemafweging — accepteer een klein, begrensd foutenpercentage in ruil voor een enorme vermindering in geheugen en I/O.