Os filtros Bloom são estruturas de dados probabilísticas usadas para testar se um elemento é um membro de um conjunto. São eficientes em termos de espaço e velocidade, tornando-os adequados para aplicações onde consultas rápidas de membros são necessárias com alguns falsos positivos aceitáveis.

Como os filtros Bloom funcionam

Um filtro Bloom usa um array de bits e várias funções de hash. Quando um elemento é adicionado, cada função de hash o mapeia para uma posição no array, configurando esses bits para 1. Para verificar se um elemento existe, as mesmas funções de hash são aplicadas, e os bits correspondentes são examinados. Se todos estiverem configurados para 1, o elemento é provável no conjunto; se algum for 0, definitivamente não é.

Cálculos para filtros Bloom

A probabilidade falsa positiva depende do tamanho do array de bits (m), do número de elementos inseridos (n) e do número de funções de hash (k). A probabilidade (p) de um falso positivo pode ser aproximada por:

p □ (1 - e]-kn/m]]]k]

Valores ideais para k e m podem minimizar falsos positivos para um dado n. Normalmente, k é escolhido como:

k = (m/n) * Em 2

Casos de uso de filtros Bloom

Os filtros Bloom são usados em vários campos, incluindo:

  • Sistemas de banco de dados para testes rápidos de adesão
  • Caching na Web para reduzir as buscas de disco
  • Sistemas distribuídos para sincronização de dados
  • Segurança da rede para filtragem de spam

Limitações de Filtros Bloom

Embora eficientes, os filtros Bloom têm limitações. Eles podem produzir falsos positivos, mas não falsos negativos. Uma vez que os bits são definidos como 1, eles não podem ser reiniciados, o que pode levar a imprecisões ao longo do tempo. Eles também não são adequados para remover elementos individuais sem estruturas de dados adicionais.