Filtros de Bloom: verificar pertenencia con memoria mínima

⏱️ Lectura: 11 min

Los filtros de Bloom son una de esas estructuras de datos que al principio parecen magia: permiten preguntar «¿está este elemento en mi conjunto?» usando una fracción minúscula de la memoria que haría falta para guardar los elementos completos. La contrapartida es elegante y, sobre todo, predecible.

📑 En este artículo

1. TL;DR
2. Qué es un filtro de Bloom
3. Cómo funcionan los filtros de Bloom por dentro
4. Ejemplo práctico en Python
5. La matemática: cuántos bits y cuántas funciones hash
6. Casos de uso reales
7. Ventajas y desventajas
8. Variantes: borrado y alternativas
9. Preguntas frecuentes
   1. ¿Por qué un filtro de Bloom nunca tiene falsos negativos?
   2. ¿Cuánta memoria ahorra realmente?
   3. ¿Puedo eliminar elementos de un filtro de Bloom?
   4. ¿Qué pasa cuando el filtro se llena?
   5. ¿En qué se diferencia de una tabla hash?
   6. ¿Las funciones hash deben ser criptográficas?
10. Referencias

A cambio de ese ahorro, un filtro de Bloom acepta algunos falsos positivos (puede decir «quizás» cuando la respuesta real era «no»), pero jamás se equivoca en sentido contrario: si responde «no está», es absolutamente cierto. Esa garantía asimétrica es justo lo que los hace tan útiles.

TL;DR

• Un filtro de Bloom responde «quizás está» o «seguro no está»: tiene falsos positivos, pero nunca falsos negativos.
• Burton Bloom lo propuso en 1970 para ahorrar memoria al verificar pertenencia a un conjunto.
• Usa un array de bits y k funciones hash; agregar y consultar son O(k), sin importar el tamaño del conjunto.
• Con unos 10 bits por elemento se logra una tasa de falsos positivos cercana al 1%.
• No permite borrar elementos ni listar su contenido; solo confirma la ausencia con certeza.
• Lo usan Cassandra, Bigtable, Chrome, las CDN y Redis para evitar búsquedas costosas en disco o red.
• Variantes como el filtro de conteo o el filtro Cuckoo añaden borrado a costa de más memoria.

Qué es un filtro de Bloom

Un filtro de Bloom es una estructura de datos probabilística diseñada para una única tarea: comprobar si un elemento pertenece o no a un conjunto. La palabra «probabilística» es clave. A diferencia de un conjunto tradicional (un set de Python o una tabla hash), no guarda los elementos reales. En su lugar guarda una especie de huella comprimida de todo lo que ha visto.

Imagina la lista de invitados de una fiesta enorme. Un portero con la lista completa puede confirmar con certeza quién está invitado, pero necesita cargar con todos los nombres. Un filtro de Bloom es como un portero que, en vez de la lista, lleva una tarjeta con marcas: para cada invitado hizo unas cuantas marcas en posiciones fijas. Cuando llega alguien, comprueba si todas sus marcas están presentes. Si falta una, lo rechaza sin dudar. Si están todas, lo deja pasar… aunque de vez en cuando colará a un colado cuyas marcas coinciden por casualidad.

Esa es la naturaleza de los filtros de Bloom: rapidísimos y diminutos, a cambio de un margen de error controlado y siempre en la misma dirección.

Cómo funcionan los filtros de Bloom por dentro

El corazón de un filtro de Bloom son dos cosas muy simples: un array de bits (todos en cero al inicio) y un conjunto de k funciones hash que convierten cualquier elemento en posiciones dentro de ese array.

Para agregar un elemento, se pasa por las k funciones hash. Cada una devuelve una posición, y en cada una de esas posiciones el filtro pone el bit en 1. Para consultar un elemento, se repite el mismo cálculo: se obtienen las k posiciones y se mira si todas valen 1. Si al menos una vale 0, el elemento definitivamente no fue agregado. Si todas valen 1, el elemento probablemente fue agregado.

graph LR
  A["Elemento: manzana"] --> B["hash1, hash2, hash3"]
  B --> C["Posiciones: 3, 17, 42"]
  C --> D["Poner esos bits a 1"]
  D --> E["Array de bits actualizado"]

La razón de los falsos positivos es intuitiva: a medida que se agregan elementos, cada vez hay más bits en 1. Llega un punto en que las k posiciones de un elemento nunca insertado coinciden, por pura colisión, con bits que otros elementos ya encendieron. El filtro dice «quizás» y se equivoca. Lo que nunca puede pasar es lo contrario: si un elemento se insertó, sus bits están en 1 a la fuerza, así que jamás recibirá un «no» falso.

💭 Clave: los falsos positivos existen, los falsos negativos no. Por eso un filtro de Bloom sirve para descartar con certeza, no para confirmar con certeza.

Ejemplo práctico en Python

Nada aclara mejor el concepto que una implementación desde cero. Este filtro de Bloom usa MD5 con una sal distinta para simular las k funciones hash (en producción se usan funciones más rápidas como MurmurHash, pero la idea es idéntica).

import hashlib

class FiltroBloom:
    def __init__(self, tamano_bits, num_hashes):
        self.tamano = tamano_bits
        self.num_hashes = num_hashes
        self.bits = [0] * tamano_bits

    def _posiciones(self, elemento):
        for i in range(self.num_hashes):
            dato = f"{elemento}-{i}".encode()
            h = int(hashlib.md5(dato).hexdigest(), 16)
            yield h % self.tamano

    def agregar(self, elemento):
        for pos in self._posiciones(elemento):
            self.bits[pos] = 1

    def podria_contener(self, elemento):
        return all(self.bits[pos] for pos in self._posiciones(elemento))


filtro = FiltroBloom(tamano_bits=1000, num_hashes=3)
filtro.agregar("manzana")
filtro.agregar("banana")

print(filtro.podria_contener("manzana"))  # True  (quizas: aqui correcto)
print(filtro.podria_contener("uva"))      # False (seguro: nunca se agrego)

Observa que el array de bits ocupa lo mismo da igual si guardas dos frutas o dos millones de claves: 1000 bits son 125 bytes. Un set con dos millones de cadenas ocuparía decenas de megabytes. Esa es la propuesta de valor de los filtros de Bloom llevada al extremo.

La matemática: cuántos bits y cuántas funciones hash

El comportamiento de un filtro de Bloom no es un misterio: se calcula con dos parámetros, el número esperado de elementos (n) y la tasa de falsos positivos que estás dispuesto a tolerar (p). A partir de ahí se derivan el tamaño óptimo del array de bits (m) y el número de funciones hash (k).

• Tamaño del array — m = -(n · ln p) / (ln 2)². Cuanto menor sea la tasa de error deseada, más bits necesitas.
• Número de funciones hash — k = (m / n) · ln 2. Existe un punto óptimo: pocas funciones dejan pasar muchos falsos positivos; demasiadas saturan el array antes de tiempo.
• Regla práctica — alrededor de 10 bits por elemento y 7 funciones hash dan una tasa de falsos positivos cercana al 1%. Para bajar al 0,1% se necesitan unos 15 bits por elemento.

Lo interesante es que estos números no dependen del tamaño de los elementos. Da igual que guardes URLs largas o números de tres dígitos: lo que importa es cuántos hay y qué error aceptas.

💡 Tip: no calcules estos parámetros a mano. Bibliotecas como pybloom-live (Python), guava (Java) o el módulo Bloom de Redis los derivan por ti a partir de n y p.

Casos de uso reales

Los filtros de Bloom no son un ejercicio académico: están en la base de sistemas que usas a diario. Su patrón siempre es el mismo: evitar una operación cara cuando se puede descartar antes con una operación barata.

• Bases de datos LSM (Cassandra, Bigtable, RocksDB) — antes de leer un archivo en disco para buscar una clave, consultan un filtro de Bloom en memoria. Si dice «no está», se ahorran la lectura de disco por completo.
• Navegadores web — Chrome usó durante años un filtro de Bloom local para descartar URLs no peligrosas sin consultar al servidor de Navegación Segura en cada clic.
• CDN y cachés — un filtro permite saber al instante si un recurso quizás está cacheado, evitando consultas innecesarias al origen.
• Sistemas de recomendación — para no volver a mostrar a un usuario contenido que ya vio, sin almacenar el historial completo.
• Detección de duplicados — rastreadores web que necesitan saber si una URL ya fue visitada sin guardar miles de millones de cadenas.

Ventajas y desventajas

Como toda herramienta, los filtros de Bloom brillan en un nicho concreto y son una mala idea fuera de él. Conviene tener clara la frontera.

• Ventaja: memoria constante — el espacio depende de la precisión, no del tamaño de los datos almacenados.
• Ventaja: velocidad — agregar y consultar son O(k), normalmente un puñado de operaciones, independientemente de cuántos elementos haya.
• Ventaja: sin falsos negativos — un «no» siempre es verdad, lo que permite descartar con total confianza.
• Desventaja: falsos positivos — un «sí» es solo «quizás», así que casi siempre hay que verificar después con la fuente real.
• Desventaja: no se borra — un filtro de Bloom clásico no permite eliminar elementos sin arriesgarse a corromper otros.
• Desventaja: no se enumera — no puedes recuperar la lista de lo que insertaste; el filtro solo responde sí/no.

⚠️ Ojo: nunca uses un filtro de Bloom como única fuente de verdad para decisiones críticas (por ejemplo, conceder acceso). Sirve para optimizar, no para autorizar.

Variantes: borrado y alternativas

La imposibilidad de borrar elementos motivó varias evoluciones de la idea original. El filtro de Bloom de conteo reemplaza cada bit por un pequeño contador: agregar incrementa, borrar decrementa. A cambio, consume varias veces más memoria. El filtro Cuckoo, más moderno, soporta borrado y suele tener mejor rendimiento con tasas de error bajas, almacenando huellas en vez de bits. Para conjuntos en disco o distribuidos existen también los filtros de cinta (ribbon filters) y los filtros XOR, que apuran aún más el ahorro de espacio.

La elección depende de tu caso: si no necesitas borrar, el filtro de Bloom clásico sigue siendo difícil de superar por su simplicidad y madurez.

📖 Resumen en Telegram: Ver resumen

Preguntas frecuentes

¿Por qué un filtro de Bloom nunca tiene falsos negativos?

Porque al agregar un elemento se ponen en 1 todas sus posiciones, y esos bits jamás vuelven a 0 en un filtro clásico. Al consultarlo más tarde, esas mismas posiciones seguirán en 1, así que el elemento nunca recibirá un «no» erróneo. El error solo aparece en sentido contrario, como falso positivo.

¿Cuánta memoria ahorra realmente?

Mucha. Con unos 10 bits por elemento (alrededor de 1,25 bytes) se obtiene un 1% de falsos positivos. Almacenar el mismo elemento como cadena en un conjunto tradicional puede costar decenas o cientos de bytes, además de la sobrecarga de la estructura. El ahorro suele ser de uno o dos órdenes de magnitud.

¿Puedo eliminar elementos de un filtro de Bloom?

No en la versión clásica: poner un bit a 0 podría afectar a otros elementos que comparten esa posición. Si necesitas borrar, usa un filtro de Bloom de conteo o un filtro Cuckoo, que están diseñados para ello a costa de más memoria.

¿Qué pasa cuando el filtro se llena?

A medida que crece la proporción de bits en 1, la tasa de falsos positivos aumenta. Por eso se dimensiona de antemano para la cantidad esperada de elementos. Si superas esa cantidad, lo correcto es reconstruir el filtro con un array más grande, no seguir agregando.

¿En qué se diferencia de una tabla hash?

Una tabla hash guarda los elementos reales y responde con exactitud, pero ocupa proporcionalmente mucho más espacio. Un filtro de Bloom no guarda los elementos, ocupa una fracción y responde de forma probabilística. Son herramientas complementarias: el filtro descarta rápido y barato; la fuente real confirma cuando hace falta.

¿Las funciones hash deben ser criptográficas?

No. De hecho conviene que no lo sean, porque la velocidad importa. Funciones como MurmurHash o FNV son habituales. Lo esencial es que distribuyan bien los valores; la seguridad criptográfica es irrelevante para este uso.

Referencias

• Burton H. Bloom (1970) — el artículo original «Space/time trade-offs in hash coding with allowable errors».
• Wikipedia: Bloom filter — visión general, fórmulas y variantes con referencias.
• Redis: Bloom filter — implementación lista para producción y su API.
• Bloom Filters by Example — tutorial interactivo para visualizar el array de bits en acción.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.