Estructuras de datos Tablas hash y grafosTema 6

Filtros de Bloom: responder rápido aceptando falsos positivos

Un filtro de Bloom contesta si un elemento pertenece a un conjunto usando una fracción de la memoria de un hash set. El precio es que a veces dice que sí cuando la respuesta era no, y la gracia es que nunca dice que no cuando la respuesta era sí.

Para este tema conviene tener claro:Tablas hash y resolución de colisiones

8 min de lectura3 bloques para tocar20 de sept de 2026

Un hash set con diez millones de URLs ocupa cientos de megabytes: guarda cada clave completa, más el costo de la tabla. Pero muchas veces no hace falta guardarlas — la pregunta no es cuál es el dato, sino ¿esto ya lo vimos?

Un filtro de Bloom responde esa pregunta con unos pocos megabytes, y lo hace aceptando un trato raro: puede decir que sí cuando la respuesta era no, pero nunca dice que no cuando la respuesta era sí. Esa asimetría es todo el diseño.

Un arreglo de bits y varias funciones de hash

La estructura es un arreglo de $m$ bits, todos en cero, y $k$ funciones de hash independientes.

Las dos operaciones

Agregar un elemento. Se calculan sus $k$ hashes, cada uno da una posición del arreglo, y esas $k$ posiciones se ponen en uno. Si ya estaban en uno, se quedan en uno: no hay contador.
Consultar un elemento. Se calculan sus mismos $k$ hashes. Si alguna de esas posiciones está en cero, el elemento seguro no está. Si todas están en uno, el elemento probablemente está.
Borrar. No se puede. Poner un bit en cero podría romper a otro elemento que comparte esa posición.

El filtro, paso a paso

Arreglo de 12 bits, todos en cero.

1 / 6

Con k = 2 funciones de hash. La consulta de «pera» da positivo sin que nadie la haya agregado: sus dos bits los prendieron «uva» y «kiwi» por separado.

Antes de seguir, predecí

¿Qué pasa si querés borrar «uva» poniendo en cero los bits 2 y 7?

Cuánta memoria y cuántos hashes

La tasa de falsos positivos no es un misterio: se elige de antemano. Con $n$ elementos, $m$ bits y $k$ funciones de hash, la probabilidad aproximada de falso positivo es

p \approx \left(1 - e^{-kn/m}\right)^{k}.

Dadas la cantidad de elementos y la tasa que se tolera, salen los dos parámetros:

m = -\frac{n \ln p}{(\ln 2)^2}, \qquad k = \frac{m}{n}\ln 2.

Tasa de falsos positivos	Bits por elemento	Funciones de hash	Diez millones de elementos
10 %	≈ 4,8	3	≈ 6 MB
1 %	≈ 9,6	7	≈ 12 MB
0,1 %	≈ 14,4	10	≈ 18 MB
0,01 %	≈ 19,2	13	≈ 24 MB

Cada orden de magnitud menos de falsos positivos cuesta unos 4,8 bits por elemento: el costo crece con el logaritmo, no con la tasa. Un hash set con esas mismas URLs son cientos de megabytes.

Más a fondo · formalPor qué k = (m/n)·ln 2

Con $k$ chico se prenden pocos bits por elemento, pero cada consulta mira pocas posiciones y es fácil que todas coincidan por azar. Con $k$ grande cada consulta es más exigente, pero el arreglo se llena de unos mucho más rápido y termina coincidiendo todo.

Entre esos dos efectos hay un mínimo. Derivando $p(k) = (1 - e^{-kn/m})^k$ respecto de $k$ e igualando a cero se llega a $k = (m/n)\ln 2$ , y con ese $k$ la proporción de bits en uno es exactamente $1/2$ . Es un resultado lindo y también un diagnóstico práctico: si contás los bits prendidos y hay muchos más que la mitad, el filtro está sobrecargado.

Dónde se usa de verdad

El filtro casi nunca es la respuesta final: es el filtro barato que evita el trabajo caro.

Sistema	Qué evita el filtro	Qué pasa con un falso positivo
Bases de datos LSM	Leer de disco un archivo que no tiene la clave	Una lectura de disco inútil, y nada más
Cachés distribuidas	Consultar a un nodo que no tiene el dato	Una consulta de red desperdiciada
Detección de duplicados en streams	Guardar todo lo visto en memoria	Se descarta como duplicado algo que era nuevo
Listas de contraseñas filtradas	Descargar y guardar la lista entera	Se rechaza una contraseña que estaba bien

La tercera y la cuarta fila muestran el criterio: el falso positivo es aceptable cuando cuesta trabajo de más, y peligroso cuando descarta datos o rechaza a un usuario.

Qué usar cuando el Bloom no alcanza

Estructura	Qué agrega	Qué cuesta
Filtro con contadores	Permite borrar	Cuatro bits o más por posición en vez de uno
Cuckoo filter	Borra y suele usar menos espacio a tasas bajas	Implementación bastante más compleja; puede fallar al insertar
HyperLogLog	Cuenta cuántos distintos hay	No contesta pertenencia: es otra pregunta
Count-Min Sketch	Estima cuántas veces apareció cada uno	Sobreestima; no contesta pertenencia exacta
Hash set	Respuesta exacta y borrado	Guarda las claves: órdenes de magnitud más memoria

Las tres del medio contestan preguntas distintas. Es el error más común de esta familia: usar la estructura probabilística equivocada para la pregunta que se tiene.

Cierre

Autoevaluación

¿Lo entendiste?

¿Qué garantiza un filtro de Bloom?

¿Por qué no se pueden borrar elementos?

Querés bajar la tasa de falsos positivos del 1 % al 0,1 %. ¿Cuánto más ocupa?

Contás los bits prendidos y hay muchos más que la mitad. ¿Qué indica?

¿En cuál de estos casos NO conviene un filtro de Bloom?