Compromissos
Ao usar um Filtro de Bloom, há um compromisso entre a eficiência de espaço e a precisão. Em troca de consumir menos memória do que estruturas de dados como tabelas de hash que fornecem respostas perfeitas todo o tempo, os Filtros de Bloom podem retornar falsos positivos.
Casos de Uso
Os Filtros de Bloom são utilizados em various casos, como:
* Bancos de dados NoSQL para reduzir leituras de disco para chaves que não existem.
* Redes de entrega de conteúdo, como Akamai, para prevenir o caching de página única (páginas web que são solicitadas apenas uma vez).
* Navegadores web, como o Chrome, para identificar URLs maliciosas.
* Validadores de senha para prevenir senhas fracas.
Como um Filtro de Bloom Funciona
Um Filtro de Bloom utiliza multiple funções de hash para mapear um elemento para múltiplos buckets em uma matriz de bits. Cada bucket contém um único bit, que começa com um 0. Quando um elemento é adicionado ao Filtro de Bloom, as funções de hash retornam os números correspondentes aos buckets para serem definidos como 1. Quando uma consulta é feita ao Filtro de Bloom, as funções de hash retornam os mesmos números, e se todos os buckets correspondentes estiverem definidos como 1, o Filtro de Bloom retorna um “provavelmente sim”. Se algum dos buckets for 0, o Filtro de Bloom retorna um “não”.
Falsos Positivos
Os falsos positivos ocorrem quando o Filtro de Bloom retorna um “provavelmente sim” para um elemento que não está realmente no conjunto. A probabilidade de falsos positivos pode ser controlada escolhendo o tamanho correto do Filtro de Bloom com base no número esperado de entradas nele.