Saltar al contenido
Omnikalc

Calculadora de filtro de Bloom

Introduce el número de elementos y la tasa de falsos positivos aceptada para obtener el tamaño del vector de bits, el número de funciones hash y la memoria necesaria.

Actualizado el
Tus datos

Valor fuera de rango

%

Valor fuera de rango

Resultados

Tamaño del vector de bits (millones de bits)

9,59

Memoria
1,20 Mo
Bits por elemento
9,59
Número de funciones hash
7
Tasa de falsos positivos con el número de funciones redondeado
1,004 %
Memoria ahorrada respecto a claves de 64 bits
85,0 %

La calculadora de filtro de Bloom da el tamaño del vector de bits, el número de funciones hash y la memoria necesarios para un número de elementos y una tasa de falsos positivos aceptados.

Cómo se hace el cálculo

  • Introduce el número de elementos que guardar.
  • Introduce la tasa de falsos positivos aceptada, en porcentaje.
  • La calculadora da los bits, la memoria, los bits por elemento, las funciones hash, la tasa real de falsos positivos y el ahorro respecto al almacenamiento de las claves.

Ejemplo

Para 1.000.000 de elementos y una tasa del 1 %, m = −10⁶ × ln 0,01 / (ln 2)² = 9,59 millones de bits, es decir, 1,20 MB, o 9,59 bits por elemento. El número óptimo de funciones es 7, y la tasa real de falsos positivos con él es de 1,004 %.

Por qué es útil

La calculadora ayuda a los desarrolladores, a los ingenieros de bases de datos y a los estudiantes a dimensionar un filtro de Bloom antes de construirlo, y a sopesar la memoria frente al número de búsquedas inútiles.

Qué debes saber

La tasa de falsos positivos sube rápido si insertas más elementos de los previstos, así que dimensiona el filtro para el número máximo de elementos. Cada vez que divides la tasa entre diez, cuesta unos 4,8 bits más por elemento. Una tasa del 0,1 % necesita unos 14,4 bits por elemento y 10 funciones. Utiliza funciones hash independientes y rápidas, o dos funciones combinadas para generar más, un truco que mantiene la calidad. Los filtros de cuco y los filtros de cociente ofrecen eliminación y un mejor aprovechamiento del espacio con tasas bajas. Un filtro colocado delante de un almacenamiento lento, como un disco o un servicio remoto, compensa cuando la mayoría de las búsquedas son de claves ausentes.

Herramientas relacionadas

La calculadora de colisiones de hash cubre el efecto de la paradoja del cumpleaños, la de pasos de búsqueda binaria cuenta las comparaciones, la de entropía de Shannon mide la información y la de tasa de aciertos de caché describe las cachés.

Preguntas frecuentes

¿Qué es un filtro de Bloom?

Un filtro de Bloom es una estructura compacta que indica si un elemento está quizá en un conjunto o seguro que no está. Pone a 1 k bits de un vector de bits por cada elemento añadido. Nunca da un falso negativo, pero puede dar un falso positivo, cuya tasa depende de los bits por elemento y de k.

¿Cómo se elige el tamaño y el número de funciones?

Para una tasa objetivo p, el tamaño óptimo es m = −n ln p / (ln 2)², es decir, unos 9,6 bits por elemento para un 1 %, y el número óptimo de funciones es k = (m / n) ln 2. La calculadora redondea k a un entero y muestra la tasa real obtenida.

¿Dónde se usan los filtros de Bloom?

Las bases de datos y los almacenes clave-valor los usan para evitar lecturas de disco de claves ausentes, los navegadores y las cachés para evitar búsquedas inútiles, y los sistemas de red para comprobar la pertenencia a bajo coste. No permiten eliminar elementos, salvo con una variante con contadores.

¿Te ha resultado útil esta calculadora?

¡Gracias por tu opinión!

Resultados orientativos con fines informativos. No sustituyen el consejo de un profesional.