Transformar inteligentemente una tabla hash en una estructura de datos probabilística para intercambiar precisión por grandes ganancias de memoria
hmesa de fresno es una de las estructuras de datos más conocidas y utilizadas. Con una elección inteligente de la función hash, una tabla hash puede producir un rendimiento óptimo para consultas de inserción, búsqueda y eliminación en tiempo constante.
El principal inconveniente de la tabla hash son las posibles colisiones. Para evitarlos, uno de los métodos estándar incluye aumentar el tamaño de la tabla hash. Si bien este enfoque funciona bien en la mayoría de los casos, a veces todavía estamos limitados en el uso de un gran espacio de memoria.
Es necesario recordar que una tabla hash siempre proporciona una respuesta correcta a cualquier consulta. Puede sufrir colisiones y ser lento a veces, pero siempre garantiza respuestas 100% correctas. Resulta que en algunos sistemas no siempre necesitamos recibir la información correcta para las consultas. Esta disminución de la precisión se puede utilizar para centrarse en mejorar otros aspectos del sistema.
En este artículo, descubriremos una estructura de datos innovadora llamada Filtro de floración. En palabras simples, es una versión modificada de una tabla hash estándar que compensa una pequeña disminución en la precisión por ganancias de espacio de memoria.
El filtro Bloom está organizado en forma de una matriz booleana de tamaño m. Inicialmente todos sus elementos están marcados como 0 (falso). Aparte de eso, es necesario elegir k funciones hash que tomen objetos como entrada y los asigne al rango [0, m — 1]. Cada valor de salida corresponderá posteriormente a un elemento de matriz en ese índice.
Para obtener mejores resultados, se recomienda que las funciones hash generen valores cuya distribución sea casi uniforme.
Inserción
Siempre que es necesario agregar un nuevo objeto, se pasa a través de k funciones hash predefinidas. Para cada valor hash de salida, el elemento correspondiente en ese índice se convierte en 1 (verdadero).
Si un elemento de matriz cuyo índice se generó a partir de una función hash ya se ha establecido en 1, entonces simplemente permanece en 1.
Básicamente, la presencia de 1 en cualquier elemento de la matriz actúa como una prueba parcial de que un elemento hash del índice de la matriz respectivo realmente existe en el filtro Bloom.
Buscar
Para comprobar si un objeto existe, se calculan sus k valores hash. Puede haber dos escenarios posibles:
Si estos son al menos uno valor hash para el cual el elemento de matriz respectivo es igual a 0, esto significa que el el objeto no existe.
Durante la inserción, un objeto se asocia con varios elementos de la matriz que están marcados como 1. Si un objeto realmente existiera en el filtro, todas las funciones hash generarían de manera determinista la misma secuencia de índices que apuntan a 1. Sin embargo, apuntar a una matriz El elemento con 0 significa claramente que el objeto actual no está presente en la estructura de datos.
Si por todos los valores hashlos respectivos elementos de la matriz son iguales a 1, esto significa que el objeto probablemente existe (no 100%).
Esta afirmación es exactamente lo que hace que el filtro Bloom sea una estructura de datos probabilística. Si se agregó un objeto antes, durante una búsqueda, el filtro Bloom garantiza que los valores hash serán los mismos para él, por lo que se encontrará el objeto.
Sin embargo, el filtro Bloom puede producir una respuesta falsa positiva cuando un objeto en realidad no existe pero el filtro Bloom afirma lo contrario. Esto sucede cuando todas las funciones hash para el objeto devuelven valores hash de 1 correspondientes a otros objetos ya insertados en el filtro.
Las respuestas falsas positivas tienden a ocurrir cuando la cantidad de objetos insertados se vuelve relativamente alta en comparación con el tamaño de la matriz del filtro Bloom.
Estimación de errores falsos positivos.
Es posible estimar la probabilidad de obtener un error falso positivo, dada la estructura del filtro de Bloom.
La prueba completa de esta fórmula se puede encontrar en Wikipedia. Basándonos en esa expresión, podemos hacer un par de observaciones interesantes:
- La probabilidad de FP disminuye con el aumento en el número de funciones hash k, el aumento en el tamaño de la matriz my la disminución en el número de objetos insertados n.
- Antes de insertar objetos en el filtro Bloom, podemos encontrar el número óptimo de funciones hash k requeridas que minimizarán la probabilidad de FP si conocemos el tamaño de la matriz my podemos estimar el número de objetos n que se insertarán en el futuro.
Otra opción para reducir la probabilidad de FP es una combinación (conjunción Y) de varios filtros Bloom independientes. En última instancia, se considera que un elemento está presente en la estructura de datos solo si está presente en todos los filtros Bloom.
Restricciones
- A diferencia de las tablas hash, la implementación estándar de un filtro Bloom no admite la eliminación.
- El número elegido de funciones hash k y el tamaño de la matriz m al principio no se pueden cambiar más adelante. Si existe tal necesidad, la única forma de hacerlo es crear otro filtro Bloom con nuevas configuraciones insertando todos los objetos previamente almacenados.
De acuerdo con la página de wikipediael filtro Bloom se usa ampliamente en sistemas grandes:
- Bases de datos como ApacheHBase, apache casandra y PostgreSQL utilice el filtro Bloom para comprobar filas o columnas no existentes. Este enfoque es considerablemente más rápido que utilizar búsquedas en disco.
- Medio utiliza el filtro Bloom para filtrar páginas que ya han sido recomendadas a un usuario.
- Google Chrome utilizó el filtro Bloom en el pasado para identificar URL maliciosas. Una URL se consideraba segura si el filtro Bloom arrojaba una respuesta negativa. De lo contrario, se realizó la verificación completa.
En este artículo, cubrimos un enfoque alternativo para construir tablas hash. Cuando una pequeña disminución en la precisión puede verse comprometida para un uso más eficiente de la memoria, el filtro Bloom resulta ser una solución sólida en muchos sistemas distribuidos.
Variar el número de funciones hash con el tamaño del filtro Bloom nos permite encontrar el equilibrio más adecuado entre precisión y requisitos de rendimiento.
Todas las imágenes, a menos que se indique lo contrario, son del autor.