Última atualização: 2026-07-13

Dimensionamento de filtro de Bloom

Um filtro de Bloom é uma forma compacta de responder a uma única pergunta: "eu provavelmente já vi este item?". Ele não guarda chaves, apenas um vetor de bits, e troca uma probabilidade pequena e ajustável de falso positivo por uma grande economia de memória. Dois números decidem seu formato — quantos itens você espera armazenar e com que frequência tolera uma correspondência falsa — e deles seguem diretamente o tamanho ótimo do vetor de bits e o número de funções de hash.

A fórmula

Para $n$ itens esperados e uma taxa de falsos positivos alvo $p$, o vetor de bits que minimiza a memória tem comprimento

O número ótimo de funções de hash é então

arredondado ao inteiro mais próximo. Aqui $m$ é o número de bits, $k$ é o número de funções de hash independentes aplicadas a cada item e $\ln 2 \approx 0{,}693$. Como $p$ é uma probabilidade menor que 1, seu logaritmo natural é negativo, então ambas as fórmulas produzem valores positivos.

Exemplo resolvido. Um filtro para um milhão de itens ($n = 1{,}000{,}000$) com alvo de 1% ($p = 0{,}01$):

Um milhão de itens a 1% custam, portanto, cerca de 1,14 MiB de memória e sete funções de hash — aproximadamente 9,6 bits por item, valor que se mantém para qualquer número de itens nessa precisão.

Bits por item e a escada de precisão

Como a fórmula do tamanho é linear em $n$, o custo de armazenamento por item, $m / n = -\ln p / (\ln 2)^2$, depende apenas da taxa alvo. Isso o torna uma medida limpa para comparar orçamentos de precisão.

Cada queda de dez vezes na taxa de falsos positivos acrescenta cerca de 4,8 bits por item e aproximadamente três funções de hash. A memória cresce apenas linearmente enquanto a taxa de erro cai geometricamente, e é isso que torna os filtros de Bloom atraentes.

Por que o número de hash importa

Com o tamanho do vetor fixo, poucas funções de hash deixam os bits esparsos e fáceis de casar por acaso, enquanto muitas enchem o vetor tão densamente que quase todos os bits ficam ativados. O ponto ótimo ativa metade dos bits e fica em $k = (m/n)\ln 2$. Como $k$ precisa ser inteiro, a calculadora o arredonda, e a taxa de falsos positivos real é recalculada a partir desse valor arredondado:

No exemplo acima, o $k = 7$ arredondado dá cerca de 1,004%, um pouquinho acima do alvo de 1% porque o $k$ ideal era 6,64 e não um inteiro.

O que um filtro de Bloom pode e não pode fazer

Um filtro de Bloom nunca produz um falso negativo: se ele diz que um item está ausente, ele realmente está. O único erro é um falso positivo, cuja taxa esta calculadora dimensiona. Filtros padrão oferecem inserção e consulta, mas não remoção, porque os bits são compartilhados entre itens — apagar os bits de um poderia corromper outros. Quando a remoção é necessária, um filtro de Bloom com contadores troca cada bit por um pequeno contador, ao custo de várias vezes a memória, e um filtro cuckoo oferece remoção com tamanho comparável.

Uma ressalva: o filtro é dimensionado para um $n$ fixo. Insira muito mais itens do que o planejado e o vetor satura, empurrando a taxa de falsos positivos acima do alvo. Se o crescimento é provável, dimensione desde o início para a quantidade maior ou use um projeto escalável que encadeia vários filtros.

O arredondamento na prática

O número de bits $m$ da fórmula raramente é um número redondo. Implementações reais alocam palavras de máquina ou páginas de memória inteiras, então arredondam $m$ para cima, o que empurra a taxa de falsos positivos alcançada um pouco abaixo do alvo — um pequeno bônus. O tamanho mostrado aqui é o mínimo teórico antes desse arredondamento.

Cálculos relacionados

Filtros de Bloom se apoiam em hashing, então a chance de dois itens compartilharem um hash é regida pela mesma matemática do aniversário — veja a Calculadora de Probabilidade de Colisão de Hash. Para identificadores de comprimento fixo, a Calculadora de Probabilidade de Colisão de UUID aplica o mesmo raciocínio aos UUIDs, e a Calculadora de Entropia de Shannon mede a informação que um conjunto de dados carrega.