Bloom Filter
Un filtro de Bloom aproxima la pertenencia a un conjunto con k funciones hash y un array de bits, ofreciendo eficiencia espacial a cambio de una tasa de falsos positivos.
Propósito
Proporcionar consultas aproximadas de pertenencia eficientes en espacio para cachés y bases de datos.
Mecanismo
Inserción: se aplica hash al elemento con k funciones y se activan los bits correspondientes. Consulta: si los k bits son 1, el elemento probablemente está presente (tasa de falsos positivos p≈(1-e^(-kn/m))^k). Nunca produce falsos negativos. La versión estándar no admite borrado.
Casos de uso
- Filtrado de caché
- Optimización de consultas de bases de datos
- Deduplicación