Što je Bloom filter i koji kompromis čini?

Question

Accepted Answer

**Bloom filter** je struktura efikasna po pitanju prostora koja je **probabilistička** i odgovara na pitanja članstva u skupu s jednom preokretom: može imati **lažno pozitivne** ali **nikada lažno negativne**. "Sigurno odsutno" je sigurno; "moguće prisutno" trebuje stvarnu provjeru.

## Kako funkcionira

Niz bitova od `m` bitova i `k` hash funkcija. Za **dodavanje** stavke, postavi `k` bitove koje ona heširuje. Za **upit**, provjeri te `k` bitove — ako je neki od njih 0, stavka je sigurno odsutna.

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

| Operacija | Vrijeme | Prostor |
|---|---|---|
| add | O(k) | O(m) bitovi |
| query | O(k) | — |

Nema lažno negativnih; stopa lažno pozitivnih pada kako `m` (i prilagođeni `k`) rastu.

## Kompromisi

- **Prednosti:** minijaturni otisak memorije u odnosu na pohranu punih ključeva; operacije konstantnog vremena.
- **Nedostaci:** lažno pozitivni; **ne može se obrisati** (standardni Bloom filter); ne može se pobrojati članove.

## Zašto je to važno

Bloom filtri jeftino preskakuju skupo posao: baze podataka (npr. Cassandra, HBase) koriste ih kako bi izbjegle čitanja s diska za ključeve koji **sigurno** nisu na disku.

Materijaliziraju klasičan kompromis sustava — prihvati mali, ograničeni stopa greške zauzvrat za ogromno smanjenje memorije i I/O-a.