Co to jest Bloom filter i jaki kompromis podejmuje?

Question

Accepted Answer

**Bloom filter** to struktura zużywająca mało przestrzeni **probabilistyczna**, która odpowiada na pytanie o przynależność do zbioru z jednym zwrotem: może mieć **fałszywe pozytywne**, ale **nigdy fałszywe negatywy**. "Zdecydowanie nie istnieje" jest pewne; "prawdopodobnie istnieje" wymaga rzeczywistego sprawdzenia.

## Jak to działa

Tablica bitów `m` bitów i `k` funkcji hash. Aby **dodać** element, ustaw `k` bitów, na które się hashuje. Aby **zapytać**, sprawdź te `k` bity — jeśli jakikolwiek jest 0, element zdecydowanie nie istnieje.

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

| Operacja | Czas | Przestrzeń |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Brak fałszywych negatywów; współczynnik fałszywych pozytywów spada wraz ze wzrostem `m` (i dostrojonego `k`).

## Dlaczego to ważne

- **Zalety:** bardzo małe wykorzystanie pamięci w porównaniu z przechowywaniem pełnych kluczy; operacje w stałym czasie.
- **Wady:** fałszywe pozytywne; **nie można usunąć** (standardowy Bloom filter); nie można wymienić członków.

## Dlaczego to ważne

Bloom filtry tanio omijają kosztowną pracę: bazy danych (np. Cassandra, HBase) używają ich, aby uniknąć odczytów z dysku dla kluczy, które **zdecydowanie** nie są na dysku.

Ucieleśniają one klasyczny kompromis systemów — zaakceptuj małą, ograniczoną szybkość błędów w zamian za ogromne zmniejszenie pamięci i I/O.