Hva er et Bloom-filter og hvilken avveining gjør det?

Question

Accepted Answer

Et **Bloom-filter** er en plasseffektiv **probabilistisk** struktur som besvarer settmedlemskapsspørsmål med en vending: det kan ha **falske positiver** men **aldri falske negativer**. "Definitivt ikke tilstede" er sikkert; "muligens tilstede" krever en reell sjekk.

## Hvordan det fungerer

En bitarray på `m` biter og `k` hash-funksjoner. For å **legge til** et element, setter du `k` bitene det hashas til. For å **spørre**, sjekker du disse `k` bitene — hvis noen er 0, er elementet definitivt fraværende.

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

| Operasjon | Tid | Plass |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Ikke falske negativer; falskt-positiv-rate faller når `m` (og innstilt `k`) vokser.

## Avveininger

- **Styrker:** bittintet minne kontra lagring av hele nøkler; konstant-tid operasjoner.
- **Svakheter:** falske positiver; **kan ikke slette** (et standard Bloom-filter); kan ikke liste medlemmer.

## Hvorfor det er viktig

Bloom-filtre hopper billig over dyrt arbeid: databaser (f.eks. Cassandra, HBase) bruker dem for å unngå disklesing for nøkler som **definitivt** ikke er på disk.

De legemliggjør en klassisk systemavveining — aksepter en liten, begrenset feilrate til gjengjeld for en massiv reduksjon i minne og I/O.