Vad är ett Bloom-filter och vilken kompromiss gör det?

Question

Accepted Answer

Ett **Bloom-filter** är en **sannolikhetsbaserad** struktur som är minneseffektiv och svarar på frågor om medlemskap i en mängd med en vridning: det kan ha **falska positiva** men **aldrig falska negativa**. "Definitivt inte närvarande" är säkert; "möjligen närvarande" kräver en faktisk kontroll.

## Hur det fungerar

En bitmatris med `m` bitar och `k` hashfunktioner. För att **lägga till** ett element sätter du `k` bitar som det hash:ar till. För **fråga** kontrollerar du dessa `k` bitar — om någon är 0 är elementet definitivt frånvarande.

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

## Kod

```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 | Tid | Utrymme |
|---|---|---|
| add | O(k) | O(m) bitar |
| query | O(k) | — |

Ingen falska negativa; andelen falska positiva minskar när `m` (och inställt `k`) växer.

## Kompromisser

- **Styrkor:** mycket litet minnesfotavtryck jämfört med lagring av fullständiga nycklar; operationer i konstant tid.
- **Svagheter:** falska positiva; **kan inte ta bort** (ett standard Bloom-filter); kan inte lista medlemmar.

## Varför det spelar roll

Bloom-filter hoppar billigt över dyrt arbete: databaser (t.ex. Cassandra, HBase) använder dem för att undvika diskläsningar för nycklar som **definitivt** inte finns på disken.

De exemplifierar en klassisk systemkompromiss — acceptera en liten, begränsad felfrekvens i utbyte mot en enorm minskning av minne och I/O.