Co je Bloom filtr a jaký kompromis vytváří?

Question

Accepted Answer

**Bloom filtr** je prostorově efektivní **pravděpodobnostní** struktura, která odpovídá na dotazy na příslušnost do množiny s jedním zvratem: může mít **falešné pozitivy**, ale **nikdy falešné negativy**. "Určitě není přítomen" je jisté; "možná přítomen" vyžaduje skutečnou kontrolu.

## Jak to funguje

Bitové pole o `m` bitech a `k` hash funkcích. Chcete-li **přidat** prvek, nastavte `k` bitů, do kterých se hash mapuje. Chcete-li se **dotazovat**, zkontrolujte ty `k` bity — pokud je některý 0, prvek je určitě nepřítomen.

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

## Kód

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

| Operace | Čas | Prostor |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Žádné falešné negativy; míra falešných pozitivů klesá s růstem `m` (a vyladěným `k`).

## Kompromisy

- **Silné stránky:** extrémně malá stopa paměti vs. ukládání úplných klíčů; operace v konstantním čase.
- **Slabé stránky:** falešné pozitivy; **nelze smazat** (standardní Bloom filtr); nelze vypsat členy.

## Proč je to důležité

Bloom filtry levně přeskakují drahé práce: databáze (např. Cassandra, HBase) je používají, aby se vyhnuly čtením z disku pro klíče, které **určitě** nejsou na disku.

Opodstatnňují klasický kompromis systémů — přijmout malou, omezenou míru chyb výměnou za obrovské snížení paměti a I/O.