Última actualización: 2026-07-13

Tamaño de filtro de Bloom

Un filtro de Bloom es una forma compacta de responder a una sola pregunta: «¿probablemente ya he visto este elemento?». No guarda claves, solo un array de bits, y cambia una probabilidad de falso positivo pequeña y ajustable por un gran ahorro de memoria. Dos números deciden su forma —cuántos elementos esperas almacenar y con qué frecuencia toleras una coincidencia falsa— y de ellos se derivan directamente el tamaño óptimo del array de bits y el número de funciones hash.

La fórmula

Para $n$ elementos previstos y una tasa de falsos positivos objetivo $p$, el array de bits que minimiza la memoria tiene longitud

El número óptimo de funciones hash es entonces

redondeado al entero más próximo. Aquí $m$ es el número de bits, $k$ es el número de funciones hash independientes aplicadas a cada elemento y $\ln 2 \approx 0{,}693$. Como $p$ es una probabilidad menor que 1, su logaritmo natural es negativo, así que ambas fórmulas producen valores positivos.

Ejemplo resuelto. Un filtro para un millón de elementos ($n = 1{,}000{,}000$) con un objetivo del 1 % ($p = 0{,}01$):

Un millón de elementos al 1 % cuestan, pues, unos 1,14 MiB de memoria y siete funciones hash: alrededor de 9,6 bits por elemento, una cifra que se mantiene para cualquier número de elementos a esa precisión.

Bits por elemento y la escalera de precisión

Como la fórmula del tamaño es lineal en $n$, el coste de almacenamiento por elemento, $m / n = -\ln p / (\ln 2)^2$, depende solo de la tasa objetivo. Eso lo convierte en una forma limpia de comparar presupuestos de precisión.

Cada caída de diez veces en la tasa de falsos positivos añade unos 4,8 bits por elemento y aproximadamente tres funciones hash. La memoria crece solo de forma lineal mientras la tasa de error cae geométricamente, y eso es lo que hace atractivos a los filtros de Bloom.

Por qué importa el número de hash

Con el tamaño del array fijo, muy pocas funciones hash dejan los bits dispersos y fáciles de coincidir por azar, mientras que demasiadas llenan el array tan densamente que casi todos los bits quedan activados. El punto óptimo activa la mitad de los bits y se sitúa en $k = (m/n)\ln 2$. Como $k$ debe ser entero, la calculadora lo redondea, y la tasa de falsos positivos real se recalcula a partir de ese valor redondeado:

En el ejemplo anterior, el $k = 7$ redondeado da alrededor del 1,004 %, un pelín por encima del objetivo del 1 % porque el $k$ ideal era 6,64 en lugar de un entero.

Lo que un filtro de Bloom puede y no puede hacer

Un filtro de Bloom nunca produce un falso negativo: si dice que un elemento no está, realmente no está. El único error es un falso positivo, cuya tasa dimensiona esta calculadora. Los filtros estándar admiten insertar y consultar, pero no eliminar, porque los bits se comparten entre elementos: borrar los bits de uno podría corromper otros. Cuando hace falta eliminar, un filtro de Bloom con contadores cambia cada bit por un pequeño contador a costa de varias veces la memoria, y un filtro cuckoo ofrece eliminación con un tamaño comparable.

Una advertencia: el filtro se dimensiona para un $n$ fijo. Inserta muchos más elementos de los previstos y el array se satura, empujando la tasa de falsos positivos por encima del objetivo. Si el crecimiento es probable, dimensiona desde el principio para la cantidad mayor o usa un diseño escalable que encadena varios filtros.

El redondeo en la práctica

El número de bits $m$ de la fórmula rara vez es redondo. Las implementaciones reales reservan palabras de máquina o páginas de memoria enteras, así que redondean $m$ al alza, lo que empuja la tasa de falsos positivos lograda algo por debajo del objetivo: un pequeño extra. El tamaño que se muestra aquí es el mínimo teórico antes de ese redondeo.

Cálculos relacionados

Los filtros de Bloom se apoyan en el hashing, así que la probabilidad de que dos elementos compartan un hash se rige por la misma matemática del cumpleaños; consulta la Calculadora de Probabilidad de Colisión de Hash. Para identificadores de longitud fija, la Calculadora de probabilidad de colisión de UUID aplica el mismo razonamiento a los UUID, y la Calculadora de entropía de Shannon mide la información que contiene un conjunto de datos.