Cómo se usa
- En el modo Tamaño para una tasa objetivo, escribe el número de elementos y la tasa de falsos positivos en porcentaje (1 significa un «sí» erróneo por cada cien consultas de elementos ausentes).
- Lee el número de bits, la memoria en bytes, KiB o MiB y el número de funciones hash.
- En el modo Tasa de un filtro, escribe n, m en bits y k para obtener la tasa de falsos positivos y el k óptimo para ese tamaño.
Cómo funciona
Un filtro de Bloom es un array de m bits. Cada elemento activa k bits elegidos por k funciones hash, y una consulta comprueba esos k bits. Las fórmulas:
- m = ⌈−n × ln p ÷ (ln 2)²⌉
- k = round(m ÷ n × ln 2), como mínimo 1
- p = (1 − e^(−k × n ÷ m))^k
Como m se redondea hacia arriba y k a un entero, la tasa real se aparta un poco del objetivo; la calculadora la muestra como Tasa con estos m y k.
Ejemplo
Un millón de elementos al 1 %:
- m = 1.000.000 × 4,6052 ÷ 0,48045 = 9.585.058,4, redondeado hacia arriba a 9.585.059 bits;
- memoria: 9.585.059 ÷ 8 = 1.198.133 bytes, es decir, 1,14 MiB;
- k = 9,585 × 0,6931 = 6,64, redondeado a 7 funciones hash;
- la tasa real con 7 funciones hash es 1,0039 %, aproximadamente un falso positivo cada 100 consultas.
Consejos
- Duplicar el tamaño del filtro no reduce la tasa a la mitad, sino que la eleva al cuadrado (aproximadamente): el 1 % pasa a ser cerca del 0,01 %.
- En el código bastan dos funciones hash para simular k: h1 + i × h2 para i = 0 … k − 1.
- Si necesitas borrar elementos, mira los filtros de Bloom con contadores o los filtros cuckoo.