Calculadora de Parâmetros do Filtro Bloom

Obtenha o tamanho ideal da matriz de bits e a quantidade de funções hash para um filtro Bloom a partir dos dois números que realmente os impulsionam — quantos itens você espera inserir e quanto ruído de falso positivo está disposto a aceitar.

Como usar

1. Digite o número esperado de itens (n) que você planeja inserir no filtro.
2. Arraste o controle deslizante de taxa de falso positivo alvo para a precisão que você precisa — valores menores significam menos falsos positivos, mas uma matriz de bits maior.
3. Leia o tamanho da matriz de bits (m), a quantidade de funções hash (k) e a memória exata necessária, além de um gráfico mostrando como a memória é dimensionada conforme você aperta a taxa de falso positivo no mesmo n.

As fórmulas

• Tamanho da matriz de bits: m = ceil(-n · ln(p) / (ln 2)²)
• Quantidade de funções hash: k = round((m / n) · ln 2), com um mínimo de 1

Estas são as derivações de parâmetros ótimos padrão usadas por todas as implementações de filtro Bloom convencionais (Guava, BF.RESERVE do Redis, pybloom). Como m e k são arredondados para números inteiros, a calculadora também relata a taxa real de falso positivo nesses valores arredondados — usando a estimativa padrão (1 - e^(-kn/m))^k — já que raramente é idêntica ao alvo que você digitou.

Lendo o gráfico

O gráfico plotar a memória necessária em relação à taxa de falso positivo alvo, em seu n inserido, em uma escala logarítmica para a taxa de falso positivo. Como m é linear em -ln(p) e o eixo x é -log₁₀(p), a troca é uma linha reta, não uma curva — apertar a taxa de falso positivo por uma ordem de magnitude custa um aumento proporcional e previsível de memória. Sua configuração atual é marcada com um ponto vermelho.

Limitações

Isto dimensiona um filtro Bloom padrão (não-contagem, não-escalável) e assume uma família hash ideal — as funções hash reais com bits correlacionados divergirão ligeiramente da taxa teórica de falso positivo. Não leva em conta a sobrecarga por bit da implementação de uma linguagem/biblioteca específica (algumas implementações arredondam m para uma potência de dois ou um múltiplo de palavra de máquina para indexação mais rápida), então trate m/memória aqui como o mínimo teórico, não necessariamente a alocação exata que sua biblioteca fará.

Privacidade

Tudo funciona no seu navegador — nada do que você digita é enviado para lugar nenhum.

Ferramentas relacionadas

Se você precisar de um hash para as chaves de armazenamento do filtro Bloom (ou qualquer outra coisa), consulte o Hash Generator. Depois que o seu filtro for dimensionado, a Cache TTL Calculator ajuda a descobrir quanto tempo suas entradas devem viver se você o estiver usando na frente de um cache.