Los filtros Bloom se ven realmente bien cuando consideras que puedes determinar si un Int está en un conjunto con un 99% de certeza en tiempo constante. Pero también pueden hacerlo los hashes, con la única diferencia de que, en un hash, la mayoría de las veces usted accede a la memoria solo una vez. Con los filtros bloom, necesita acceder a ellos 7 veces por solicitud en lugares completamente distantes , por lo que tendrá varias faltas de caché por solicitud.
¿Me estoy perdiendo algo?
Te estás perdiendo cómo las dos estructuras de datos tratan las colisiones de hash. Los filtros de bloom no almacenan los valores reales, por lo que el espacio requerido es el tamaño constante de la matriz designada. En cambio, si usas un hash tradicional, trata de almacenar todos los valores que le das, para que crezca con el tiempo.
Considere una función hash simplificada (¡solo para un ejemplo!) f(x) = x % 2 . Ahora ingresa los siguientes enteros: 2, 3, 4, 5, 6, 7 .
Hash estándar: los valores dados se harán con hash, y terminamos con muchas colisiones debido a f(2) = f(4) = f(6) = 0 y f(3) = f(5) = f(7) = 1 . Sin embargo, el hash almacena todos estos valores y podrá decirle que 8 no está almacenado en él. ¿Como hace eso? Realiza un seguimiento de las colisiones y almacena todos los valores con el mismo valor hash, luego, cuando lo consulta, además compara su consulta. Así que consultemos el mapa para 8 : f(8) = 0 , para que se vea en un grupo donde ya hemos insertado 2, 4, 6 y necesitamos hacer 3 comparaciones para decirle que 8 no era parte del entrada.
Filtro Bloom: Normalmente, cada valor de entrada se revisa contra k funciones hash diferentes. Nuevamente, para simplificar, supongamos que solo usamos la función de hash único f . Necesitamos una matriz de 2 valores entonces y cuando encontramos la entrada 2 significa que debido a f(2) = 0 establecemos el valor de la matriz en la posición 0 al valor 1 . Lo mismo sucede con 4 y 6 . De manera similar, las entradas 3, 5, 7 establecen la posición del conjunto 1 en el valor 1 . Ahora consultamos si 8 era parte de la entrada: f(8) = 0 y la matriz en la posición 0 es 1 , por lo que el filtro de floración afirmará falsamente que 8 era parte de la entrada.
Para ser un poco más realista, consideremos que agregamos una segunda función de hash g(x) = x % 10 . Con eso, el valor de entrada 2 conduce a dos valores hash f(2) = 0 y g(2) = 2 y las dos posiciones de matriz correspondientes se establecerán en 1 . Por supuesto, la matriz ahora debe ser al menos de tamaño 10 . Pero cuando consultamos 8 , verificaremos la matriz en la posición 8 debido a g(8) = 8 , y esa posición seguirá siendo 0 . Es por eso que las funciones hash adicionales disminuyen los falsos positivos que obtendrá.
Comparación: El filtro "bloom" usa k funciones hash, lo que significa que se puede acceder a hasta k de posiciones aleatorias de la matriz. Pero esa cifra es exacta. El hash, en cambio, solo le garantiza un tiempo de acceso constante amortizado, pero puede des-generar dependiendo de la naturaleza de su función de hash y los datos de entrada. Por lo tanto, generalmente es más rápido, excepto en los casos des-generados.
Sin embargo, una vez que tenga una colisión de hash, el hash estándar tendrá que verificar la igualdad de los valores almacenados con el valor de consulta. Esta verificación de igualdad puede ser arbitrariamente costosa y nunca se producirá con un filtro de floración.
En términos de espacio, el filtro bloom es constante, ya que nunca hay necesidad de usar más memoria que la matriz designada. Por otro lado, el hash crece dinámicamente y puede ser mucho más grande debido a tener que realizar un seguimiento de los valores colisionados.
Compensación: Ahora que sabe lo que es barato y lo que no, y en qué circunstancias, debería poder ver la compensación. Los filtros Bloom son excelentes si desea detectar muy rápidamente que un valor se ha visto anteriormente, pero puede vivir con falsos positivos. Por otro lado, puede elegir el mapa hash si desea una corrección garantizada al precio de no poder juzgar exactamente su tiempo de ejecución, pero puede aceptar casos degenerados ocasionalmente que pueden ser mucho más lentos que el promedio.
Del mismo modo, si se encuentra en un entorno de memoria limitada, es posible que desee preferir los filtros de floración para su garantía de uso de memoria.
Los casos de uso para los filtros de floración y hashes son distintos y en su mayoría desarticulados, por lo que la comparación directa no tiene sentido. Además, dependerá de los detalles técnicos de las implementaciones, ya que hay muchas formas de manejar las colisiones de hash con diferentes compromisos.
El filtro de floración puede responder si el elemento está en un conjunto para conjuntos enorme , con una probabilidad razonable, pero no exactamente, usando una cantidad modesta de memoria. Enormes, como, trillones de elementos. Pero nunca son exactos. Solo puede reducir la cantidad de falsos positivos utilizando más memoria o más funciones hash.
Por otro lado, las tablas hash son exactas, pero necesitan almacenar el conjunto. Entonces, trillones de elementos requerirían terrabytes de memoria (y eso es solo trillones americanos). También pueden almacenar datos adicionales para cada elemento, lo que los filtros de floración no pueden.
Por lo tanto, los filtros "bloom" se usan cuando tiene un método lento de obtener datos para algún miembro (que involucra consultas con el servidor, lecturas del disco y demás) de un conjunto grande (que no cabe en la memoria o no es práctico transferir) al cliente o similar) y desea evitar ejecutar la operación lenta para los objetos que no están en el conjunto.
Lea otras preguntas en las etiquetas data-structures