Filtro de floración

Solución:

Si los datos se almacenan en la memoria en Java, la estructura de algoritmo más simple es HashMap. HashMap se utiliza para determinar si la clave existe y, por tanto, si los datos existen. Al utilizar el algoritmo hash para buscar elementos, la complejidad del tiempo es básicamente O (1) (puede haber situaciones en las que los conflictos hash se conviertan en listas vinculadas o árboles rojo-negro, y se puede ignorar el impacto en la complejidad del tiempo).

Usar el almacenamiento HashMap es rápido y sencillo, y se puede utilizar en la mayoría de escenarios. Pero HashMap ocupa mucho espacio:

Por qué aparece Bloom Filter:

Por ejemplo:

Por ejemplo, si se almacenan 100.000 enteros en la memoria, el espacio ocupado es de 4x32x1000000 bits, es decir 1220 megas. Por ejemplo, el filtro Bloom se almacena en 4 bytes (después de que el filtro Bloom calcula los datos a través de múltiples hashes ->; el hash se especifica varias veces de acuerdo con la cantidad de datos, lo que genera múltiples datos y ocupa múltiples bits), luego el ocupado el espacio es 610M. Menos de la mitad del espacio original.

Personalmente, creo que este tipo de contraste es particularmente efectivo al contrastar personajes.

Hay muchos caracteres en una cadena. Dependiendo de la codificación, un carácter tiene dos o tres bytes, por ejemplo 10 caracteres. El almacenamiento de cadenas ocupa 20 bytes y la ocupación de memoria de información de clase relacionada con cadenas.

Almacenamiento de bits, cálculo flexible basado en el tamaño de los datos y el número de hash. Por ejemplo, 4 bytes, que es una quinta parte del espacio ocupado por el hashMap original.

Definir un vector de bytes

Primero, defina una matriz de bytes de longitud especificada (matriz de bytes, el valor de cada elemento en la matriz).

Si la longitud es 8 (tamaño de un byte), todos los valores de los elementos son 0 de forma predeterminada, como se muestra a continuación:

(2) Calcular el valor hash

Para que los datos se escriban en el filtro, se obtienen múltiples valores hash de acuerdo con un cierto número de funciones hash, y luego se determina a su vez el índice correspondiente a cada valor hash.

Si se utilizan tres funciones hash, se calculan tres valores hash y se determina que los vectores de bytes correspondientes a los valores hash son 1, 3 y 7.

(3) Actualizar el vector de bytes

Cambie el índice calculado del vector de bytes a 1 (si antes era 0 o 1, se cambió a 1). Como se muestra a continuación:

(1) Calcular el valor hash

Es necesario determinar si hay datos en el filtro y obtener múltiples valores hash de acuerdo con un cierto número de funciones hash y luego determine secuencialmente el índice correspondiente a cada valor hash.

Si se utilizan tres funciones hash, se calculan tres valores hash y se determina que los vectores de bytes correspondientes a los valores hash son 1, 3 y 7.

Nota: La forma de determinar la función hash y calcular el índice debe ser exactamente la misma que cuando se escriben datos.

(2) Determinar si existe

Por ejemplo, en la matriz de bytes original, los valores de los elementos correspondientes a 1, 3 y 7 son todos 1. Se determina que el elemento puede existir, pero si el valor de un elemento no es 1, se determina que el elemento no debe existir.

El objetivo principal del filtro Bloom es garantizar que la tasa de errores de juicio esté dentro del rango establecido dentro del número de datos especificado. La tasa de falsos positivos es demasiado alta, los datos no se pueden filtrar y la tasa de falsos positivos no puede ser cero.

Por lo tanto, es necesario calcular dos datos para satisfacer la cantidad de datos almacenados y la tasa de falsos positivos:

Un factor decisivo al utilizar el filtro Bloom es que la velocidad de inserción Los datos y la consulta de datos deben ser muy rápidos. Entonces, al realizar hash de datos, debemos elegir un algoritmo de hash rápido.

Y el algoritmo hash, el orden y el algoritmo para escribir datos y consultar datos deben ser completamente consistentes.

A mejorar. . . . .

El filtro Bloom se puede implementar fácilmente en la memoria a través de Guava de Google.

No es necesario calcular manualmente la longitud y el número de hash de la matriz de bytes. Solo necesita ingresar la cantidad de datos que se ingresarán y la tasa de error de cálculo esperada.

Sin ingresar la tasa de falsos positivos esperada, la tasa de falsos positivos es 0.03, es decir, al verificar 100 datos fuera de rango, se juzgará que hay alrededor de tres datos.

Después de ejecuciones repetidas, los resultados son consistentes. Según los resultados, se considera que:

El almacenamiento de memoria es limitado y los mapas de bits en Redis se pueden utilizar para almacenar matrices de bytes.

Utilice redis para implementar el filtro Bloom. Debe calcular manualmente la longitud de la matriz de bytes y el número de hashes de acuerdo con la fórmula.

El proceso de implementación necesita mejoras. . . . . .