I filtri Bloom sono strutture di dati probabilistiche utilizzate per verificare se un elemento è un membro di un insieme. Sono efficienti in termini di spazio e velocità, rendendoli adatti per applicazioni in cui le domande di adesione rapide sono richieste con alcuni falsi positivi accettabili.

Come funziona Bloom Filtri

Quando viene aggiunto un elemento, ogni funzione hash lo mappa a una posizione nell'array, impostando quei bit a 1. Per verificare se esiste un elemento, vengono applicate le stesse funzioni hash e vengono esaminate le corrispondenti bit. Se tutte sono impostate su 1, l'elemento è probabile nel set; se uno è 0, non lo è.

Calcoli per filtri Bloom

La falsità positiva dipende dalla dimensione del bit array (m), dal numero di elementi inseriti (n), e dal numero di funzioni hash (k). La probabilità (p) di un falso positivo può essere approssimata da:

p ≈ (1 - e-kn/m[]]] ]]]] ]

I valori ottimali per k e m possono ridurre al minimo i falsi positivi per una data n. Normalmente, k è scelto come:

k = (m/n) * ln 2

Utilizzare i casi di filtri Bloom

I filtri Bloom sono utilizzati in vari campi, tra cui:

  • Sistemi di database per test di appartenenza rapido
  • Caching Web per ridurre le ricerche su disco
  • Sistemi distribuiti per la sincronizzazione dei dati
  • Sicurezza della rete per il filtraggio dello spam

Limitazioni di filtri Bloom

I filtri Bloom sono efficienti e possono produrre falsi positivi ma non falsi negativi. Una volta impostati i bit a 1, non possono essere ripristinati, che possono portare a imprecisioni nel tempo. Inoltre non sono adatti per eliminare singoli elementi senza ulteriori strutture di dati.