Uma das minhas estruturas de dados favoritas para operações de busca eficientes é o filtro de Bloom, acabei de encontrar esta demonstração, confira lá.

Nomeado em homenagem ao seu criador, Burton Howard Bloom, um filtro de Bloom é uma estrutura de dados probabilística eficiente em termos de espaço, projetada para responder a uma pergunta simples: “Este item está no conjunto?”. Ao contrário de outras estruturas de dados, um filtro de Bloom compensa a precisão pela velocidade e eficiência de espaço, o que significa que às vezes pode retornar falsos positivos, mas nunca falsos negativos.

O filtro de Bloom funciona usando um vetor de bits de tamanho ‘m’ e ‘k’ funções de hash. Quando um elemento é adicionado ao filtro, ele é passado por todas as ‘k’ funções de hash, que retornam ‘k’ índices para definir como ‘1’ no vetor de bits. Para verificar se um elemento está no filtro, as mesmas ‘k’ funções de hash são aplicadas. Se todos os ‘k’ índices no vetor de bits forem ‘1’, o filtro retorna ‘sim’; caso contrário, retorna ‘não’. Uma resposta ‘sim’ pode significar que o elemento definitivamente não está no conjunto (verdadeiro negativo) ou pode estar no conjunto (falso positivo), mas uma resposta ‘não’ sempre significa que o elemento não está no conjunto (verdadeiro negativo). Note que ao implementar você deve pensar cuidadosamente quantas funções de hash utilizar e qual a taxa aceitável de falsos positivos.

Filtros de Bloom são amplamente utilizados em aplicações de software onde o custo de falsos positivos é menos crítico do que os benefícios de velocidade e eficiência de espaço. Algumas dessas aplicações incluem corretores ortográficos, roteadores de rede, bancos de dados e caches. Eu tenho um aplicativo gerador de senhas e uso Filtro de Bloom para verificar se uma senha já foi usada.