Un Bloom filter è una struttura probabilistica efficiente nello spazio che risponde all'appartenenza a un insieme con un aspetto cruciale: può avere falsi positivi ma mai falsi negativi. "Definitivamente non presente" è certo; "possibilmente presente" richiede un controllo reale.
Un array di bit di bit e funzioni hash. Per un elemento, impostare i bit a cui esegue l'hash. Per , controllare quei bit — se uno è 0, l'elemento è definitivamente assente.
mkkkbits: [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"
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)
| Operazione | Tempo | Spazio |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |
Nessun falso negativo; il tasso di falsi positivi diminuisce con m (e k ottimizzato).
I Bloom filter evitano a buon mercato lavoro costoso: i database (ad es. Cassandra, HBase) li usano per evitare letture da disco per chiavi che definitivamente non sono su disco.
Incarnano un classico compromesso dei sistemi — accettare un piccolo tasso di errore limitato in cambio di una riduzione enorme della memoria e dell'I/O.