Qué es el Bloom 필터?

Hablamos de una estructura de datos no tan común pero que tiene casos de uso interesantes, ademas es una buena opción cuando queremos reducir el uso de memoria. Como es un filtro, la respuesta esperada es si por lo que estoy preguntando, se encuentra o no guardado en nuestros sistemas.

Con esto en mente, tenemos que saber que es una estructura probabilística, con dos resultados posibles, estos son:

Seguro que no ❌

아마 🤞

Si nos dice que no, es que no está y eso es seguro, pero no puede garantizar que sí, entonces si la respuesta es probablemente si vamos a tener que asegurarnos yendo a verificar por segunda vez, pero a otro lugar, no al filtro. Esto se puede dar por colisiones en funciones hash y también en que, al reducer el espacio en memoria, las collisones van a estar presentes.

Ahora vemos como funciona

Hablamos de probabilidades, hashes, colisiones y demás, vamos a explicar con un caso concreto.

Supongamos que no quiere recomendarte un post que ya leíste en el ultimo tiempo, entonces, vamos a ir cargando los posts vistos en el filtro de una manera specific, que ahora detallamos.

Para nuestro filtro vamos a usar un arreglo (slice si sos gopher) con un numero que sepamos, en este caso 100, así no crece indiscriminadamente porque la idea principal es mantener nuestro uso de memoria, bajo. Usamos bool para는 0 y 1을 나타냅니다.
Cada función de hash (podemos usar varias, recomiendo fuertemente más de una) va a devolver un numero entero como resultado y cada entrada va a ser Representative por n números siendo n la cantidad de hash que usemos. Después todos los resultados van a traducirse en que ese mismo indice, va a quedar en true. Por ejemplo si tenemos un slice de 10 de bool y las tres funciones nos devuelven 2, 3 y 6 nos queda algo así:[f][f][✅​][✅​][f][f][✅​][f][f][f]
엔톤스...

var filter [100] bool //100 para tener una buena distribución

Ahora las funciones 해시

var h1 = func(i interface{}) int{...}
var h2 = func(i interface{}) int{...}
var h3 = func(i interface{}) int{...}

Si bien son placeholders, la idea es que tome cualquier valor y devuelva un entero que esté dentro del rango, por eso vamos a aplicar el operator modulo a la respuesta. Cualquier implementación que usemos, tenemos que saber que el resultado tiene que ser siempre el mismo ante la misma entrada, como una función pura y determinística.

index1 := h1("dev.to/post-x") % 100
index2 := h2("dev.to/post-y") % 100
index3 := h3("dev.to/post-z") % 100

filter[index1] = true
filter[index2] = true
filter[index3] = true

De esta manera ya queda resuelto como podemos escribir un bloom filter, para la lectura, básicamente es lo mismo, pero debemos preguntar si los indices son true y ahi tenemos cómo podemos estudiar las respuestas que vimos previamente.

Si algún indice nos da falso, sabemos que la URL que enviamos no esta en nuestro filtro.

Si todos los indices dan verdadero, decimos que probablemente si, ya que, al tener un array "chico"y que las funciones hash tienen collisones, puede que otra URL haya generado los mismos números o algo mas fácil, puede ser este ejemplo:
La url 1 nos da el resultado 1, 3 y 6
La url 2 nos da el resultado 2, 5 y 7
la url 3 nos da el resultado 2, 3 y 7 -> nos da que sí son todos true, pero la url 3 en sí, no estaba guardada, por eso en el segundo check (puede ser una base de datos) nos da que 아니 에스타바.

결론

El bloom filter es una buena opción para cuando queremos ahorrar tiempo y espacio. 캐시에서 해시맵으로 변경하는 방법을 사용하면 메모리에서 작업을 수행하고 빨간색으로 제거할 수 있습니다. Espero que lo prueben en sus proyectos!

이제 곧!

추신: sponsoreame aca si te gusto el contenido