Hvad er et Bloom filter, og hvilken afvejning gør det?

Question

Accepted Answer

Et **Bloom filter** er en pladsbesparende **probabilistisk** datastruktur, der besvarer sætmedlemskapsspørgsmål med en drejning: det kan have **falske positive**, men **aldrig falske negative**. "Definitivt ikke til stede" er sikker; "muligvis til stede" kræver en ægte kontrol.

## Sådan fungerer det

Et bitarray på `m` bits og `k` hashfunktioner. For at **tilføje** et element skal du indstille de `k` bits, det hashes til. For at **forespørge**, tjek de `k` bits — hvis nogen er 0, er elementet helt sikkert fravær.

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

## Kode

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

| Handling | Tid | Plads |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Ingen falske negative; falsk-positiv-rate falder som `m` (og tunet `k`) vokser.

## Afvejninger

- **Styrker:** tiny memory footprint vs lagring af fulde nøgler; constant-time operationer.
- **Svagheder:** falske positive; **kan ikke slette** (et standard Bloom filter); kan ikke vise medlemmer.

## Hvorfor det betyder noget

Bloom filters springer billigt dyrt arbejde over: databaser (f.eks. Cassandra, HBase) bruger dem til at undgå diskl­æsninger for nøgler, der **definitivt** ikke er på disken.

De legemliggør en klassisk systemafvejning — accepter en lille, afgrænset fejlrate i bytte for en enorm reduktion i hukommelse og I/O.