Skip to content

BloomFilter ​

BloomFilter implementa una estructura probabilística de pertenencia a conjuntos para claves string. Un BloomFilter(k, m) almacena claves en m bits usando k funciones de hash independientes: contains nunca reporta un falso negativo, pero puede reportar un falso positivo con una probabilidad que disminuye a medida que crece el número de bits por clave. No es genérico: ambos argumentos del constructor son usize.

Construcción ​

SintaxisDescripción
BloomFilter(k, m)Crea un nuevo filtro vacío con k funciones de hash sobre m bits

Métodos ​

MétodoFirmaDevuelveDescripción
insert(key: string) => voidvoidAgrega key al filtro
contains(key: string) => booleanbooleanSi key puede haber sido insertada; nunca es un falso negativo

Complejidad ​

OperaciónComplejidad Temporal
insertO(k)
containsO(k)
BloomFilter(k, m)O(m / 64 + k)

Ejemplos ​

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

El hashing es determinista, así que las ausencias anteriores están garantizadas, no son probabilísticas. contains sigue permitiendo falsos positivos en general: cuando el filtro está denso, una clave ausente puede compartir todas las k posiciones de bits con claves insertadas.