Skip to content

BloomFilter ​

BloomFilter implementa uma estrutura probabilística de pertinência em conjuntos para chaves string. Um BloomFilter(k, m) armazena chaves em m bits usando k funções de hash independentes: contains nunca reporta falso negativo, mas pode reportar um falso positivo com probabilidade que diminui à medida que o número de bits por chave cresce. Ela não é genérica: ambos os argumentos do construtor são usize.

Construção ​

SintaxeDescrição
BloomFilter(k, m)Cria um novo filtro vazio com k funções de hash sobre m bits

Métodos ​

MétodoAssinaturaRetornaDescrição
insert(key: string) => voidvoidAdiciona key ao filtro
contains(key: string) => booleanbooleanSe key pode ter sido inserida; nunca é falso negativo

Complexidade ​

OperaçãoComplexidade Temporal
insertO(k)
containsO(k)
BloomFilter(k, m)O(m / 64 + k)

Exemplos ​

insert ​

tyrus
import { BloomFilter } from "tyrus:algorithm";

const bf = BloomFilter(3, 256);
bf.insert("apple");
bf.insert("banana");
bf.insert("cherry");
bf.insert("date");

contains ​

tyrus
const bf = BloomFilter(3, 256);
bf.insert("apple");
bf.insert("banana");
bf.insert("cherry");
bf.insert("date");

print(bf.contains("apple"));   // true
print(bf.contains("banana"));  // true
print(bf.contains("egg"));     // false
print(bf.contains("fig"));     // false
print(bf.contains("grape"));   // false
print(bf.contains("honey"));   // false

O hashing é determinístico, então as falhas acima são garantidas, não probabilísticas. contains ainda permite falsos positivos em geral: quando o filtro está denso, uma chave ausente pode compartilhar todas as k posições de bits com chaves inseridas.