Diferencia entre filtros Bloom y Hashtable

HashTable:  
Hashtable está diseñado para usar una función especial llamada función Hash que se usa para mapear un valor dado con una clave particular para un acceso más rápido a los elementos. Se utiliza cuando se requieren búsquedas rápidas (bajo suposiciones razonables, el tiempo promedio para la búsqueda de elementos en una tabla hash es O(1)). El diccionario en Python se implementa usando HashTables. Java también implementa la clase HashTable
Algunas aplicaciones de hashing se pueden encontrar aquí

Filtro Bloom: 
un filtro Bloom es una estructura de datos probabilísticos eficiente en el espacio que se utiliza para probar si un elemento es miembro de un conjunto. Se usa cuando solo necesitamos saber si el elemento pertenece al objeto o no. Un filtro bloom utiliza k funciones hash y una array de n bits, donde el bit de array establecido en 0 significa que el elemento no existe y 1 indica que el elemento está presente. Algunas aplicaciones de los filtros bloom son: 

  • Google Bigtable, Apache HBase y Apache Cassandra y PostgreSQL usan filtros Bloom para reducir las búsquedas en el disco de filas o columnas inexistentes. Evitar costosas búsquedas en disco aumenta considerablemente el rendimiento de una operación de consulta de base de datos.
  • El navegador web Google Chrome solía usar un filtro Bloom para identificar URL maliciosas. Cualquier URL se comparaba primero con un filtro Bloom local, y solo si el filtro Bloom devolvía un resultado positivo, se realizaba una verificación completa de la URL (y se advertía al usuario, si eso también arrojaba un resultado positivo).

Veamos la diferencia entre tablas hash y filtros bloom:

No. S. Tablas hash Filtros de floración
1 En la tabla hash, el objeto se almacena en el depósito (posición de índice en la tabla hash) al que se asigna la función hash. Los filtros Bloom no almacenan el objeto asociado. Simplemente dice si está allí en el filtro de floración o no.
2 Las tablas hash son menos eficientes en cuanto al espacio. Los filtros Bloom son más eficientes en cuanto al espacio. su tamaño es incluso menor que el objeto asociado que está mapeando.
3 Admite eliminaciones. No es posible eliminar elementos de los filtros de floración.
4 Las tablas hash dan resultados precisos.  Los filtros Bloom tienen una pequeña probabilidad de falso positivo. (Falso positivo significa que podría estar en el filtro de floración, pero en realidad no lo está).
5 En una tabla hash, debemos implementar múltiples funciones hash o tener una función hash fuerte para minimizar las colisiones. Un filtro bloom utiliza muchas funciones hash. No hay necesidad de manejar las colisiones.
6 Las tablas hash se utilizan en operaciones de compilación, lenguajes de programación (estructuras de datos basadas en tablas hash), verificación de contraseña, etc. Los filtros Bloom encuentran aplicación en los enrutadores de red, en los navegadores web (para detectar las URL maliciosas), en los verificadores de contraseñas (para no establecer una lista débil o adivinable de contraseñas prohibidas), etc.

Los HashTables y los filtros de floración están estrechamente relacionados entre sí, por lo tanto, es aconsejable comparar estas dos estructuras de datos y usarlas sabiamente según las demandas de su aplicación/necesidad.
 

Publicación traducida automáticamente

Artículo escrito por MuskanKalra1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *