Um filtro Bloom é uma estrutura probabilística eficiente em espaço que responde a pertenças de conjunto com uma reviravolta: pode ter falsos positivos mas nunca falsos negativos. "Definitivamente não presente" é certo; "possivelmente presente" requer uma verificação real.
Um array de bits de bits e funções hash. Para um item, configure os bits para os quais ele faz hash. Para , verifique esses bits — se algum for 0, o item está definitivamente ausente.
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)
| Operação | Tempo | Espaço |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |
Sem falsos negativos; a taxa de falsos positivos diminui conforme m (e k ajustado) crescem.
Os filtros Bloom baratamente pulam trabalho caro: bancos de dados (ex. Cassandra, HBase) os usam para evitar leituras de disco para chaves que definitivamente não estão no disco.
Eles incorporam um trade-off clássico de sistemas — aceite uma pequena taxa de erro limitada em troca de uma redução massiva em memória e I/O.