Ce este un Bloom filter și ce compromis face acesta?

Question

Accepted Answer

Un **Bloom filter** este o structură **probabilistică** eficientă din punct de vedere al spațiului care răspunde la apartenența în set cu o întoarcere: poate avea **fals-pozitive** dar **niciodată fals-negative**. "Definitiv nu este prezent" este sigur; "posibil prezent" necesită o verificare reală.

## Cum funcționează

O matrice de biți de `m` biți și `k` funcții hash. Pentru a **adăuga** un element, setați `k` biții la care el face hash. Pentru a **interoga**, verificați acei `k` biți — dacă vreunul este 0, elementul este sigur absent.

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

| Operație | Timp | Spațiu |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Nici un fals-negativ; rata fals-pozitivelor scade pe măsură ce `m` (și `k` ajustat) cresc.

## Compromisuri

- **Puncte forte:** amprenta de memorie minusculă versus stocarea cheilor complete; operații în timp constant.
- **Puncte slabe:** fals-pozitive; **nu poate șterge** (un filtru Bloom standard); nu poate enumera membri.

## De ce este important

Bloom filter-ele omit ieftin lucrări scumpe: bazele de date (de ex. Cassandra, HBase) le folosesc pentru a evita citirile de disc pentru chei care **sigur** nu sunt pe disc.

Ele încarnează un compromis clasic al sistemelor — acceptați o rată de eroare mică și mărginită în schimbul unei reduceri masive în memorie și I/O.