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.