Um filtro de Bloom pode economizar consultas a disco quando a maioria das chaves buscadas está ausente. Uma resposta negativa permite pular a leitura, desde que o filtro reflita todas as inserções. Uma resposta positiva precisa ser confirmada na fonte dos dados.

Calcule uma capacidade inicial

Com m bits, n inserções e k posições de hash por chave, uma aproximação comum para a taxa de falsos positivos é (1 − exp(-kn/m))^k. Ela supõe posições uniformes e usa uma aproximação para a ocupação dos bits. Para 100 mil chaves, 1 milhão de bits e sete posições por chave, a estimativa é de cerca de 0,82%.

Se dobrar o número de chaves e mantiver o mesmo filtro, o resultado sobe para cerca de 13,8%. A diferença mostra por que a capacidade deve acompanhar o volume inserido.

Teste com chaves que você sabe que estão ausentes

Insira um conjunto controlado e consulte outro conjunto disjunto. Conte positivos no segundo conjunto e divida pelo número de consultas. Consulte também todas as chaves inseridas. Uma negativa nesse grupo indica erro de implementação, inconsistência entre escrita e leitura ou perda de estado. Limpar diretamente os bits de uma chave removida pode afetar outras chaves que usam as mesmas posições.

Bloom, Space/time trade-offs in hash coding with allowable errors

Leia também: Hashing consistente e redistribuição de chaves no anel