Mikä on Bloom-suodatin ja mikä kompromissi se tekee?

Question

Accepted Answer

**Bloom-suodatin** on tila-tehokas **todennäköisyysperustainen** rakenne, joka vastaa joukon jäsenyyskysymyksiin yhdellä käänteellä: se voi sisältää **väärät positiiviset tulokset**, mutta **ei koskaan väärät negatiiviset tulokset**. "Varmasti ei läsnä" on varma; "mahdollisesti läsnä" vaatii todellisen tarkistuksen.

## Kuinka se toimii

Bittitaulukko, jossa on `m` bittiä ja `k` hash-funktiota. **Lisätäksesi** elementin, aseta `k` bitit, joihin se heijastuu. **Kyselyä** varten tarkista nämä `k` bitit — jos jokin on 0, elementti on varmasti poissa.

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

## Koodi

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

| Toiminto | Aika | Tila |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Ei väärää negatiivisia; väärän positiivisen osuus pienenee `m`:n (ja säädetyn `k`:n) kasvaessa.

## Kompromissit

- **Vahvuudet:** pieni muistijalanjälki vs. täysien avainten varastointi; vakioaikaiset operaatiot.
- **Heikkoudet:** väärät positiiviset tulokset; **ei voi poistaa** (tavallinen Bloom-suodatin); ei voi luetella jäseniä.

## Miksi se on tärkeää

Bloom-suodattimet välttävät halvalla kallista työtä: tietokannat (esim. Cassandra, HBase) käyttävät niitä välttääkseen levyn lukemista avaimille, jotka **varmasti** eivät ole levyllä.

Ne ruumiillistavat klassisen järjestelmäkompromissin — hyväksy pieni, rajoitettu virheprosentti vastineeksi valtavasta muistin ja I/O:n vähennyksestä.