¿Cuáles son algunas aplicaciones prácticas de hashing?

Hashing es un mundo en sí mismo.

Una búsqueda rápida en google, y te verás aterrizar en Wikipedia – Hashing. El contenido presente allí es rico y bastante exhaustivo.

Intentaré darle la aplicación de hashing en bases de datos. De lo que se sabe mucho menos.

Considere que está ejecutando este pequeño fragmento lindo de SQL en una base de datos:

  ** Una tabla para capturar población en todas las ciudades del país **

 CREATE TABLE simple_table (
	 s_no INTEGER,
	 ciudad VARCHAR (20),
	 estado VARCHAR (20),
	 población INTEGER
 );

 ** Insertar algunos datos **

 ** Consulta para averiguar la población agrupada por 'estado' **
 SELECCIONE SUMA (población) DESDE simple_table GROUP BY estado;

Casi todas las bases de datos relacionales se reducen a un montón de funciones C que están altamente optimizadas.

Dada la consulta anterior, la base de datos tiene que encontrar una manera de agrupar datos. Para darle una imagen clara, suponga que tenemos los siguientes datos en nuestra base de datos:

(Fuente: mi teléfono)

Ahora mi pregunta es: ¿cómo agrega la base de datos los datos presentes en la columna de población agrupando por estado ? (Para aquellos que no conocen la agrupación, significa que no puede agregar el valor de población de las filas 1 y 2 en la imagen anterior. Dado que tienen diferentes claves de agrupación, es decir, diferentes valores de estado. Debe agregar solo aquellos valores que tengan valores de estado idénticos)

Una respuesta directa sería: Ordenar los datos según los valores de las columnas de estado para que podamos ejecutar un ciclo for simple para agregar los datos (es decir , el valor del campo de población ) en cada iteración.

¡Guay! Tenemos la respuesta Un análisis rápido del algoritmo anterior producirá una complejidad de tiempo de O (nlogn) (Combinar -ordenar / ordenar rápido) donde ‘ n’ es el número de filas.

La pregunta del billón de dólares es: ¿podemos hacerlo mejor?

¡Si podemos! Hashing al rescate.

Podemos hacer un hash del valor de la columna de estado en una tabla de hash y cada vez que encontramos hashes similares, simplemente los agregamos. No explicaré sobre el proceso de hash ya que esta pregunta asume que sabes de qué se trata el hash.

Aquí hay una pequeña interpretación:

Si analizamos la complejidad del tiempo, veremos que el hash se ejecuta en tiempo O (n) . Lo cual es mucho mejor que el enfoque basado en la clasificación.

Pero prácticamente, si seguimos exactamente el mismo enfoque que se da aquí, terminaremos obteniendo una complejidad temporal que se encuentra entre O (n) y O (nlogn) . Esto se debe a que puede haber claves con diferentes valores pero con el mismo valor hash. Estos se llaman sinónimos hash.

Por ejemplo, si usamos una función hash simple, como “módulo 10 ″ para nuestro ejemplo anterior, el valor de la columna de estado ‘A’ y ‘K’ se dividirá en el cubo 0 (suponiendo que ‘A’ es 0 y ‘K’ es 10) Esto quizás se deba a nuestra mala elección de la función hash. Podemos evitar esto eligiendo una alternativa más sólida, pero para mil millones de filas definitivamente necesitamos incorporar algún tipo de estrategia de recuperación de fallas que se encargue de este escenario. Hacemos esto simplemente usando una de las técnicas de colisión hash (como encadenamiento, sondeo, etc.). Esto corresponde a un golpe de rendimiento en nuestro análisis de complejidad de tiempo.

Entonces, ¿cómo pasamos del enfoque basado en la clasificación al enfoque basado en hash dentro de algunas líneas de esta respuesta?

Aquí está la intuición (intentaré mantenerlo lo más lúcido posible). En el enfoque basado en la ordenación, en realidad no requerimos el orden de las filas en función de su clave de agrupación (la columna de estado ). Hicimos la clasificación porque indirectamente ayuda a agregar las filas más tarde. Así que podemos considerar esto como algún tipo de trabajo extra, que corresponde al término ‘ nlogn’ . Necesitamos alguna forma de realizar un seguimiento de los valores clave de agrupación que ya hemos visto. Entonces, si está bien usar el almacenamiento auxiliar, es decir, si estamos dispuestos a intercambiar espacio por una ganancia adicional en el tiempo, entonces podemos mantener una lista de verificación de filas que ya hemos visto. Pensar en estas líneas lo llevará a una estructura de datos de tabla hash.

Nota para los expertos en tecnología : podemos usar el método de conteo para ordenar los datos en tiempo O (n) . Pero eso usa el concepto de hashing. Aplacemos su discusión a alguna otra respuesta.

Para reflexionar: el enfoque basado en hash no siempre es mejor que el enfoque basado en la clasificación. Te dejaré preguntándote ‘¿Por qué?’

A2A, así que aquí valen mis dos centavos.

Curiosamente, he encontrado un problema con Windows, específicamente que he alcanzado el número máximo de gráficos permitidos en el sistema de Windows. He solucionado el problema con el hash.

Lo que sucedió fue que mi aplicación puede tener un número ilimitado ilimitado de mapas de bits, donde la mayoría de ellos son duplicados. Inicialmente, utilicé un enfoque de fuerza bruta y almacené todo en la memoria.

Sin embargo, después de las pruebas de carga, encontré el error y mi solución fue hacer hash de los mapas de bits y almacenarlos en un diccionario. Esto me permitió almacenar 10,000 mapas de bits únicos .

Esto debería ser suficiente para mi aplicación, ya que es bastante inconcebible que mis usuarios creen tantos mapas de bits únicos. Normalmente solo usarán los valores predeterminados.

Y, por cierto, los mapas de bits hash tienen problemas de rendimiento, pero palidecen en comparación con el otro problema.

Las tablas hash generalmente se usan para implementar matrices asociativas debido a su constante búsqueda e inserción de tiempo amortizado. Hashing se utiliza en ellos para indexar y recuperar elementos.

El hash como método se usa para comparar cadenas generando hash rodante como parte del algoritmo Rabin-Karp.

Los algoritmos de hash (funciones de hash) se usan ampliamente en criptografía. Estas incluyen las funciones hash de resumen de mensaje como MD5, que se utiliza para generar firmas digitales en un valor más corto llamado resumen de mensaje.

Hash constante, se utiliza un tipo especial de hash para asignar valores a máquinas de caché.

Una aplicación que vemos todos los días pero que ignoramos es cuando descargamos archivos, vemos algunos términos como suma de verificación MD5, suma de verificación TCP . Hashing juega un papel muy importante aquí.

Estos términos están relacionados con los paquetes de datos que recibimos del servidor o de algún otro cliente. Nos aseguramos de que los paquetes de datos que estamos recibiendo sean auténticos y legítimos mediante la aplicación de una suma de verificación. El hash se refiere a una técnica en la que tenemos una entrada de longitud variable y una salida de longitud fija donde cada entrada válida se asigna a una salida.

Digamos que estás descargando una canción. Se divide en 10 partes antes de ser transmitido. Cada paquete tiene un valor hash asociado (es encriptado y complejo, por lo que no es fácil para un intermediario alterar los datos). Cuando recibimos los datos, vemos que el valor hash del paquete de datos anterior debe coincidir con el paquete actual. Si coincide, recibimos los datos y los guardamos; de lo contrario, los descartamos.

Si todo va bien, obtienes tu canción completa. Si incluso un hash falla, la descarga falla.