Filtros de Bloom

Membresía aproximada de conjunto en unos cuantos bits por elemento. Falsos positivos, pero NUNCA falsos negativos.

Array de bits + k hashes

• Agregar: hashea de k formas, enciende esos k bits en 1 (los bits solo se PRENDEN)
• Consultar: los k bits encendidos → "probablemente presente"; cualquier 0 → "definitivamente ausente"
• Un bit en 0 PRUEBA la ausencia → sin falsos negativos, nunca
• No guarda elementos, solo su sombra de bits → tamaño independiente del tamaño del elemento

Mira el agregar y el consultar

Agrega cat/dog/fox → los bits se encienden. Consulta cat → todos encendidos → sí. 'hycr' nunca se agregó, pero sus 3 bits están todos encendidos → FALSO POSITIVO.

Cien veces menos memoria

1M de llaves al 1% de FPR: Bloom 1.2 MB, set 122 MB → 100× más chico (9.6 bits/elemento, k=7).

La fórmula de diseño

• FPR ≈ (1 − e^(−kn/m))^k
• k óptima = (m/n)·ln2 → el array termina ~medio lleno
• Bits por elemento ≈ 1.44·log₂(1/p) — depende SOLO de la tasa de error, no del tamaño del elemento
• No se puede borrar, no se puede enumerar, no se puede sobrellenar

Lo que te llevas

La exactitud es un recurso que puedes gastar — cambia un poco de error por mucho espacio. La idea fundacional de las estructuras probabilísticas (HyperLogLog, count-min sketch). Sigue: skip lists — rendimiento de árbol balanceado a base de volados.