Explicación sobre el hash y su uso para la compresión de datos.

Question

Me enfrento a una aplicación que utiliza hashing, pero aún no puedo entender cómo funciona. Aquí está mi problema, el hash se usa para generar algún índice, y con esos índices accedo a diferentes tablas, y después de agregar el valor de cada tabla que obtengo usando los índices y con eso obtengo mi valor final. Esto se hace para reducir los requisitos de memoria. La entrada a la función de hashing está haciendo el XOR entre un número constante aleatorio y algunos parámetros de la aplicación.

¿Es esta una aplicación de hashing típica? Lo que no entiendo es cómo usar el hashing podemos reducir los requisitos de memoria. ¿Alguien puede aclarar esto?

Gracias

Answer 1

El hash solo no tiene nada que ver con la memoria.

Para lo que se usa a menudo es una tabla hash. Las tablas hash funcionan calculando el hash de lo que está quitando, que luego se utiliza como índice en una estructura de datos.

Hashing le permite reducir la clave (cadena, etc.) en un valor más compacto como un entero o un conjunto de bits.

Ese podría ser el ahorro de memoria al que se refiere: reducir una clave grande a un entero simple.

Tenga en cuenta, sin embargo, que los hashes no son únicos. Un buen algoritmo de hash minimiza las colisiones, pero no está destinado a reducirse a un valor único; no es posible hacerlo (por ejemplo, si su hash genera un entero de 32 bits, su hash tendría solo 2 ^ 32 valores únicos).

Answer 2

¿Está hablando de un filtro de floración ? Esto utiliza funciones hash para obtener una forma eficiente de espacio para probar la pertenencia de un conjunto. Si es así, vea el enlace para obtener una explicación.

Answer 3

La mayoría de las buenas implementaciones de hash son ineficientes en la memoria, de lo contrario habría más informática involucrada, y eso sería exactamente perder el punto de hash.

Las implementaciones de hash se utilizan para la eficiencia del procesamiento, ya que le proporcionarán un tiempo de ejecución constante para operaciones como inserción, eliminación y recuperación.

Puede pensar en la calidad del hash de manera que todos sus datos, sin importar el tipo o tamaño, siempre estén representados en un solo formulario de longitud fija.

Answer 4

Esto podría explicarse si el hash que se está haciendo no es construir una verdadera tabla hash, sino simplemente crear un índice en una tabla de cadenas / bloques de memoria. Si tuvo la misma cadena (o secuencia de memoria) 20 veces en sus datos, y luego reemplazó las 20 instancias de esa cadena con solo su índice hash / table, podría lograr la compresión de datos de esa manera. Sin embargo, si hay una cadena de colisión real contenida en esa tabla para cada valor hash, entonces lo que acabo de describir no es lo que está sucediendo; en ese caso, la razón del hash probablemente sería acelerar la ejecución (al proporcionar un acceso rápido a los valores almacenados), en lugar de la compresión.