¿Los filtros de floración son realmente más rápidos que los hash, incluso teniendo en cuenta el caché?

Los filtros Bloom se ven realmente bien cuando considera que puede determinar si un Int está en un conjunto con un 99% de certeza en tiempo constante. Pero también pueden los hashes, con la única diferencia de que, en un hash, la mayoría de las veces está accediendo a la memoria solo una vez. Con los filtros de floración, debe acceder a ellos ~ 7 veces por solicitud en lugares completamente distantes , por lo que tendrá varios errores de caché por solicitud.

¿Me estoy perdiendo de algo?

Te estás perdiendo cómo las dos estructuras de datos manejan las colisiones hash. Los filtros de floración no almacenan los valores reales, por lo que el espacio requerido es el tamaño constante de la matriz designada. En cambio, si usa un hash tradicional, intenta almacenar todos los valores que le da, por lo que crece con el tiempo.

Considere una función hash simplificada (¡solo por un ejemplo!) f(x) = x % 2. Ahora introduzca los siguientes números enteros: 2, 3, 4, 5, 6, 7.

Hash estándar: los valores dados serán hash, y terminamos con muchas colisiones debido a f(2) = f(4) = f(6) = 0y f(3) = f(5) = f(7) = 1. Sin embargo, el hash almacena todos estos valores y podrá decirle que 8no 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, también compara su consulta. Entonces, consultemos el mapa 8: f(8) = 0para que busque en un cubo donde ya lo hemos insertado 2, 4, 6y necesita hacer 3 comparaciones para decirle que 8no era parte de la entrada.

Filtro Bloom: normalmente, cada valor de entrada se compara con kdiferentes funciones hash. Nuevamente, por simplicidad, supongamos que solo usamos la función hash única f. Necesitamos una matriz de 2 valores y cuando encontremos la entrada 2significa que debido a f(2) = 0que establecemos el valor de la matriz en la posición 0del valor 1. Lo mismo sucede para 4y 6. Del mismo modo, 3, 5, 7cada una de las entradas establece la posición de la matriz 1en valor 1. Ahora preguntamos si 8era parte de la entrada: f(8) = 0y la matriz en la posición lo 0es 1, por lo que el filtro de floración afirmará falsamente que 8fue parte de la entrada.

Para ser un poco más realista, consideremos que agregamos una segunda función hash g(x) = x % 10. Con eso, el valor de entrada 2conduce a dos valores de hash f(2) = 0y g(2) = 2y las dos posiciones de la red correspondientes se fijarán a 1. Por supuesto, la matriz ahora debe tener al menos el tamaño 10. Pero cuando consultamos 8, verificaremos la matriz en la posición 8debido 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 kBloom utiliza funciones hash, lo que significa que se puede kacceder a posiciones de matriz aleatorias. Pero esa cifra es exacta. En cambio, el hash solo le garantiza un tiempo de acceso constante amortizado, pero puede degenerar dependiendo de la naturaleza de su función hash y datos de entrada. Por lo tanto, suele ser más rápido, a excepción de los casos degenerados.

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 la consulta. Esta verificación de igualdad puede ser arbitrariamente costosa y nunca ocurrirá con un filtro de floración.

En términos de espacio, el filtro de floración 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 crecer mucho más debido a tener que hacer un seguimiento de los valores colisionados.

Compensación: ahora que sabe qué es barato y qué no, y bajo qué circunstancias, debería poder ver la compensación. Los filtros Bloom son excelentes si desea detectar rápidamente que se ha visto un valor anteriormente, pero puede vivir con falsos positivos. Por otro lado, puede elegir el mapa hash si desea garantizar la corrección al precio de no poder juzgar exactamente su tiempo de ejecución, pero puede aceptar casos ocasionalmente degenerados que pueden ser mucho más lentos que el promedio.

Del mismo modo, si se encuentra en un entorno de memoria limitado, es posible que desee preferir los filtros de floración para garantizar su uso de memoria.

Los casos de uso para filtros de floración y hashes son distintos y en su mayoría disjuntos, 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 hash con diferentes compensaciones.

El filtro de floración puede responder si el elemento está en un conjunto para grandes conjuntos, con una probabilidad razonable, pero no exactamente, usando una cantidad modesta de memoria. Enormes, como, billones 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, billones de elementos requerirían terrabytes de memoria (y eso es solo billones americanos) También pueden almacenar datos adicionales para cada elemento, que los filtros de floración no pueden.

Por lo tanto, los filtros de floración se usan cuando tiene un método lento para obtener datos para algún miembro (que implica consultar el servidor, las lecturas del disco y demás) de un conjunto grande (que no cabe en la memoria o no es práctico transferirlo al cliente o tal) y desea evitar ejecutar la operación lenta para objetos que no están en el conjunto.