Hashing en la estructura de datos: función, técnicas [con ejemplos]

Introducción

Hashing es una estructura de datos importante diseñada para resolver el problema de encontrar y almacenar datos de manera eficiente en una matriz. Por ejemplo, si tiene una lista de 20000 números y ha dado un número para buscar en esa lista, escaneará cada número en la lista hasta que encuentre una coincidencia.

Requiere una cantidad significativa de su tiempo para buscar en toda la lista y localizar ese número específico. Este proceso manual de escaneo no solo requiere mucho tiempo sino que también es ineficiente. Con hash en la estructura de datos, puede reducir la búsqueda y encontrar el número en segundos.

Este blog le brindará una comprensión más profunda del método hash, las tablas hash y el sondeo lineal con ejemplos.

¿Qué es Hashing en la estructura de datos?

Hashing en la estructura de datos es una técnica de mapeo de una gran cantidad de datos en tablas pequeñas mediante una función hash. También se conoce como la función de resumen de mensajes. Es una técnica que identifica de forma única un artículo específico de una colección de artículos similares.

Utiliza tablas hash para almacenar los datos en un formato de matriz. Cada valor en la matriz tiene asignado un número de índice único. Las tablas hash utilizan una técnica para generar estos números de índice únicos para cada valor almacenado en un formato de matriz. Esta técnica se llama la técnica hash.

Solo necesita encontrar el índice del elemento deseado, en lugar de buscar los datos. Con la indexación, puede escanear rápidamente la lista completa y recuperar el elemento que desee. La indexación también ayuda en las operaciones de inserción cuando necesita insertar datos en una ubicación específica. No importa cuán grande o pequeña sea la tabla, puede actualizar y recuperar datos en segundos.

Hashing en una estructura de datos es un proceso de dos pasos.

1. La función hash convierte el elemento en un pequeño número entero o valor hash. Este entero se utiliza como índice para almacenar los datos originales.
2. Almacena los datos en una tabla hash. Puede usar una clave hash para localizar datos rápidamente.

Ejemplos de hashing en la estructura de datos

Los siguientes son ejemplos de la vida real de hashing en la estructura de datos :

• En las escuelas, el maestro asigna un número de lista único a cada estudiante. Más tarde, el maestro usa ese número de lista para recuperar información sobre ese estudiante.
• Una biblioteca tiene un número infinito de libros. El bibliotecario asigna un número único a cada libro. Este número único ayuda a identificar la posición de los libros en la estantería.

Pago: clasificación en la estructura de datos

Función hash

La función hash en una estructura de datos asigna un tamaño arbitrario de datos a datos de tamaño fijo. Devuelve los siguientes valores: un valor entero pequeño (también conocido como valor hash), códigos hash y sumas hash.

hash = hashfunc(clave)

índice = hash % array_size

La función has debe cumplir los siguientes requisitos:

• Una buena función hash es fácil de calcular.
• Una buena función hash nunca se atasca en la agrupación y distribuye las claves de manera uniforme en la tabla hash.
• Una buena función hash evita la colisión cuando dos elementos o elementos se asignan al mismo valor hash.

Tabla de picadillo

Hashing en la estructura de datos utiliza tablas hash para almacenar los pares clave-valor. La tabla hash luego usa la función hash para generar un índice. Hashing utiliza este índice único para realizar operaciones de inserción, actualización y búsqueda.

¿Cómo funciona Hashing en la estructura de datos?

En hashing, la función hash asigna cadenas o números a un valor entero pequeño. Las tablas hash recuperan el elemento de la lista mediante una función hash. El objetivo de la técnica de hashing es distribuir los datos de manera uniforme en una matriz. Hashing asigna a todos los elementos una clave única. La tabla hash utiliza esta clave para acceder a los datos de la lista.

La tabla hash almacena los datos en un par clave-valor. La clave actúa como una entrada para la función hash. La función hash luego genera un número de índice único para cada valor almacenado. El número de índice mantiene el valor que corresponde a esa clave. La función hash devuelve un valor entero pequeño como salida. La salida de la función hash se denomina valor hash.

Entendamos el hashing en una estructura de datos con un ejemplo. Imagine que necesita almacenar algunos elementos (dispuestos en un par clave-valor) dentro de una tabla hash con 30 celdas.

Los valores son: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

La tabla hash tendrá el siguiente aspecto:

Lea también: Tipos de estructuras de datos en Python

Técnicas de Resolución de Colisiones

El hash en la estructura de datos cae en una colisión si a dos claves se les asigna el mismo número de índice en la tabla hash. La colisión crea un problema porque se supone que cada índice en una tabla hash almacena solo un valor. Hashing en la estructura de datos utiliza varias técnicas de resolución de colisiones para gestionar el rendimiento de una tabla hash.

Sondeo lineal

Hashing en la estructura de datos da como resultado un índice de matriz que ya está ocupado para almacenar un valor. En tal caso, el hashing realiza una operación de búsqueda y busca linealmente la siguiente celda vacía.

Ejemplo de sondeo lineal

Imagine que le han pedido que almacene algunos elementos dentro de una tabla hash de tamaño 30. Los elementos ya están ordenados en un formato de par clave-valor. Los valores dados son: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

El hash(n) es el índice calculado mediante una función hash y T es el tamaño de la tabla. Si el índice de ranura = (hash(n) % T) está lleno, buscamos el siguiente índice de ranura sumando 1 ((hash(n) + 1) % T). Si (hash(n) + 1) % T también está lleno, entonces intentamos (hash(n) + 2) % T. Si (hash(n) + 2) % T también está lleno, entonces intentamos (hash( n) + 3) % T.

La tabla hash tendrá el siguiente aspecto:

Hashing doble

La técnica de doble hash utiliza dos funciones hash. La segunda función hash entra en uso cuando la primera función provoca una colisión. Proporciona un índice de compensación para almacenar el valor.

La fórmula para la técnica de doble hash es la siguiente:

(firstHash(clave) + i * secondHash(clave)) % sizeOfTable

Donde i es el valor de compensación. Este valor de compensación se mantiene incrementado hasta que encuentra una ranura vacía.

Por ejemplo, tiene dos funciones hash: h1 y h2. Debe realizar los siguientes pasos para encontrar un espacio vacío:

1. Verifique si hash1 (clave) está vacío. En caso afirmativo, almacene el valor en esta ranura.
2. Si hash1 (clave) no está vacío, busque otra ranura usando hash2 (clave).
3. Verifique si hash1 (clave) + hash2 (clave) está vacío. En caso afirmativo, almacene el valor en esta ranura.
4. Siga incrementando el contador y repita con hash1(clave)+2hash2(clave), hash1(clave)+3hash2(clave), y así sucesivamente, hasta que encuentre una ranura vacía.

Ejemplo de hash doble

Imagina que necesitas almacenar algunos elementos dentro de una tabla hash de tamaño 20. Los valores dados son: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1(n) + ih2(n)) módulo 20

Conclusión

El hashing doble tiene un alto costo de cálculo, pero busca el siguiente espacio libre más rápido que el método de sondeo lineal. Los ejemplos dados en el artículo son solo para fines explicativos. Puede modificar las declaraciones anteriores según sus requisitos. En este blog, aprendimos sobre el concepto de hashing en la estructura de datos .

Puede probar el ejemplo para fortalecer su conocimiento de la estructura de datos. Si tiene curiosidad por saber más sobre la estructura de datos , consulte el programa upGrad Executive PG en el curso Full Stack Development . Este curso está diseñado para profesionales que trabajan y ofrece una formación rigurosa y colocación laboral en las mejores empresas.