Was ist ein Bloom filter und welchen Kompromiss geht er ein?

Question

Accepted Answer

Ein **Bloom filter** ist eine speichereffiziente **probabilistische** Datenstruktur, die Abfragen zur Mengenzu­gehörig­keit mit einer Wendung beantwortet: Er kann **Falsch­positive** haben, aber **niemals Falsch­negative**. "Definitiv nicht vorhanden" ist sicher; "möglicherweise vorhanden" erfordert eine echte Überprüfung.

## Funktionsweise

Ein Bitarray aus `m` Bits und `k` Hash­funktionen. Um ein Element zu **hinzufügen**, setzen Sie die `k` Bits, zu denen es gehasht wird. Um **abzu­fragen**, überprüfen Sie jene `k` Bits — wenn eines 0 ist, ist das Element garantiert nicht vorhanden.

```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 | Zeit | Platz |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Keine Falschen Negative; die Falschpositivrate sinkt mit wachsendem `m` (und justiertem `k`).

## Kompromisse

- **Stärken:** extrem kleine Speicher­abdrücke vs. Speicherung vollständiger Schlüssel; Operationen in konstanter Zeit.
- **Schwächen:** Falschpositive; **kann nicht gelöscht werden** (ein Standard Bloom filter); Mitglieder können nicht aufgelistet werden.

## Warum es wichtig ist

Bloom filters umgehen günstig teure Arbeit: Datenbanken (z. B. Cassandra, HBase) nutzen sie, um Fest­plattenlese­zugriffe für Schlüssel zu vermeiden, die **definitiv** nicht auf der Festplatte sind.

Sie verkörpern einen klassischen Systems­kompromiss — akzep­tieren Sie eine kleine, begrenzte Fehler­quote im Austausch für eine massive Reduk­tion von Speicher und I/O.