El filtro Bloom cambió unas pocas respuestas erróneas por un uso de memoria mínimo

Cuando un conjunto de elementos es enorme, almacenar cada clave es imposible, pero aun así se necesita saber si algo está en él. El ejemplo de Bloom era un diccionario de 500.000 palabras en el que solo el 10% de las palabras usan reglas de separación silábica costosas: la comprobación sensata consistía en evitar un acceso a disco, pero el diccionario era demasiado grande para un hash sin errores en la memoria disponible.

Un filtro Bloom lo resuelve con un arreglo de bits y varias funciones hash. Añadir un elemento activa los bits en esas posiciones, y la comprobación pregunta si todos están activados. Si alguno es cero, el elemento está definitivamente ausente, así que no hay falsos negativos; si todos están activados, el elemento puede estar en el conjunto o puede simplemente haber colisionado con otros elementos, produciendo un falso positivo.

Como el error es unilateral y ajustable, la estructura se mantiene pequeña mientras sigue eliminando la mayoría de las lecturas de disco innecesarias. Un área de hash de solo el 18% del tamaño que necesitaría un hash sin errores eliminó el 87% de los accesos a disco, y menos de diez bits por elemento dan una tasa de falsos positivos de aproximadamente el 1%.

Permitir que un arreglo de bits diga «quizá», nunca «no» por error

Los falsos positivos son aceptables cuando el coste es solo una comprobación adicional, pero un «no» falso perdería datos.

Un arreglo de bits con unas pocas funciones hash almacena la pertenencia en unos pocos bits por elemento.

Elimina la mayoría de las costosas consultas a disco o a la red sin almacenar el conjunto real.

Si es aceptable una pequeña probabilidad de decir que sí pero un no falso no lo es, acepta deliberadamente el error unilateral; permitir unos pocos falsos positivos suele ser la única forma de hacer caber un conjunto enorme en memoria.

Los filtros Bloom se extendieron por bases de datos, cachés, correctores ortográficos y enrutamiento de red para evitar consultas costosas, y aparecen en sistemas desde PostgreSQL y Apache Cassandra hasta Chromium y la caché a gran escala; el truco subyacente de aceptar un error unilateral a cambio de espacio es ahora una primitiva estándar en los sistemas informáticos.