Tabla hash en la estructura de datos: ejemplo de Python

¿Qué es el hash?

Un hash es un valor que tiene una longitud fija y se genera mediante una fórmula matemática. Los valores hash se utilizan en compresión de datos, criptología, etc. En la indexación de datos, los valores hash se utilizan porque tienen un tamaño de longitud fijo independientemente de los valores que se utilizaron para generarlos. Hace que los valores hash ocupen un espacio mínimo en comparación con otros valores de diferentes longitudes.

Una función hash emplea un algoritmo matemático para convertir la clave en un hash. Se produce una colisión cuando una función hash produce el mismo valor hash para más de una clave.

En este tutorial de algoritmos, aprenderá:

• ¿Qué es el hash?
• ¿Qué es una tabla hash?
• Funciones hash
• Cualidades de una buena función hash
• Colisión
• Operaciones de tabla hash
• Ejemplo de Python de tabla hash
• Explicación del código de la tabla hash
• Ejemplo de diccionario de Python
• Análisis de complejidad
• Aplicaciones del mundo real
• Ventajas de las tablas hash
• Desventajas de las tablas hash

¿Qué es una tabla hash?

Una TABLA HASH es una estructura de datos que almacena valores mediante un par de claves y valores. A cada valor se le asigna una clave única que se genera mediante una función hash.

El nombre de la clave se utiliza para acceder a su valor asociado. Esto hace que la búsqueda de valores en una tabla hash sea muy rápida, independientemente del número de elementos en la tabla hash.

Funciones hash

Por ejemplo, si queremos almacenar registros de empleados, y cada empleado se identifica de forma única mediante un número de empleado.

Podemos usar el número de empleado como clave y asignar los datos del empleado como valor.

El enfoque anterior requerirá espacio libre adicional del orden de (m * n ² ) donde la variable m es el tamaño de la matriz y la variable n es el número de dígitos del número de empleado. Este enfoque introduce un problema de espacio de almacenamiento.

Una función hash resuelve el problema anterior obteniendo el número de empleado y usándolo para generar un valor entero hash, dígitos fijos y optimizando el espacio de almacenamiento. El propósito de una función hash es crear una clave que se utilizará para hacer referencia al valor que queremos almacenar. La función acepta el valor que se va a guardar y luego utiliza un algoritmo para calcular el valor de la clave.

El siguiente es un ejemplo de una función hash simple

h(k) = k1 % m

AQUÍ,

• h (k) es la función hash que acepta un parámetro k. El parámetro k es el valor para el que queremos calcular la clave.
• k ₁ % m es el algoritmo de nuestra función hash, donde k1 es el valor que queremos almacenar y m es el tamaño de la lista. Usamos el operador de módulo para calcular la clave.

Ejemplo

Supongamos que tenemos una lista con un tamaño fijo de 3 y los siguientes valores

[1,2,3]

Podemos utilizar la fórmula anterior para calcular las posiciones que debería ocupar cada valor.

La siguiente imagen muestra los índices disponibles en nuestra tabla hash.

Paso 1)

Calcule la posición que ocupará el primer valor así

h (1) = 1% 3

= 1

El valor 1 ocupará el espacio en el índice 1

Paso 2)

Calcula la posición que ocupará el segundo valor

h (2) = 2% 3

= 2

El valor 2 ocupará el espacio en el índice 2

Paso 3)

Calcula la posición que ocupará el tercer valor.

h (3) = 3% 3

= 0

El valor 3 ocupará el espacio en el índice 0

Resultado final

Nuestra tabla hash completa ahora será la siguiente.

Cualidades de una buena función hash

Una buena función hash debe tener las siguientes cualidades.

• La fórmula para generar el hash debe utilizar el valor de los datos que se almacenarán en el algoritmo.
• La función hash debe generar valores hash únicos incluso para los datos de entrada que tienen la misma cantidad.
• La función debería minimizar el número de colisiones. Las colisiones ocurren cuando se genera el mismo valor para más de un valor.
• Los valores deben distribuirse de forma coherente entre todos los hash posibles.

Colisión

Se produce una colisión cuando el algoritmo genera el mismo hash para más de un valor.

Veamos un ejemplo.

Supongamos que tenemos la siguiente lista de valores

[3,2,9,11,7]

Supongamos que el tamaño de la tabla hash es 7 y usaremos la fórmula (k ₁ % m) donde m es el tamaño de la tabla hash.

La siguiente tabla muestra los valores hash que se generarán.

Llave	Algoritmo hash (k 1 % m)	Valor hash
3	3% 7	3
2	3% 7	2
9	3% 7	2
11	3% 7	4
7	3% 7	0

Como podemos ver en los resultados anteriores, los valores 2 y 9 tienen el mismo valor hash y no podemos almacenar más de un valor en cada posición.

El problema dado se puede resolver utilizando encadenamiento o sondeo. Las siguientes secciones tratan el encadenamiento y el sondeo en detalle.

Encadenamiento

El encadenamiento es una técnica que se utiliza para resolver el problema de la colisión mediante el uso de listas enlazadas, cada una de las cuales tiene índices únicos.

La siguiente imagen visualiza cómo se ve una lista encadenada

Tanto el 2 como el 9 ocupan el mismo índice, pero se almacenan como listas enlazadas. Cada lista tiene un identificador único.

Beneficios de las listas encadenadas

Los siguientes son los beneficios de las listas encadenadas:

• Las listas encadenadas tienen un mejor rendimiento al insertar datos porque el orden de inserción es O (1).
• No es necesario cambiar el tamaño de una tabla hash que usa una lista encadenada.
• Puede acomodar fácilmente una gran cantidad de valores siempre que haya espacio libre disponible.

Sondeo

La otra técnica que se utiliza para resolver una colisión es el sondeo. Cuando usamos el método de sondeo, si ocurre una colisión, simplemente podemos seguir adelante y encontrar una ranura vacía para almacenar nuestro valor.

Los siguientes son los métodos de sondeo:

Método	Descripción
Palpado lineal	Tal como sugiere el nombre, este método busca espacios vacíos linealmente comenzando desde la posición donde ocurrió la colisión y avanzando. Si se llega al final de la lista y no se encuentra ningún espacio vacío. El sondeo comienza al principio de la lista.
Sondeo cuadrático	Este método utiliza expresiones polinomiales cuadráticas para encontrar el siguiente espacio libre disponible.
Hash doble	Esta técnica utiliza un algoritmo de función hash secundaria para encontrar el siguiente espacio libre disponible.

Usando nuestro ejemplo anterior, la tabla hash después de usar el sondeo aparecería de la siguiente manera:

Operaciones de tabla hash

A continuación, se muestran las operaciones compatibles con las tablas Hash:

• Inserción : esta operación se usa para agregar un elemento a la tabla hash
• Búsqueda : esta operación se usa para buscar elementos en la tabla hash usando la clave
• Eliminar : esta operación se usa para eliminar elementos de la tabla hash

Insertar operación de datos

La operación de inserción se utiliza para almacenar valores en la tabla hash. Cuando se almacena un nuevo valor en la tabla hash, se le asigna un número de índice. El número de índice se calcula utilizando la función hash. La función hash resuelve cualquier colisión que se produzca al calcular el número de índice.

Búsqueda de operación de datos

La operación de búsqueda se utiliza para buscar valores en la tabla hash utilizando el número de índice. La operación de búsqueda devuelve el valor que está vinculado al número de índice de búsqueda. Por ejemplo, si almacenamos el valor 6 en el índice 2, la operación de búsqueda con el índice número 2 devolverá el valor 6.

Eliminar operación de datos

La operación de eliminación se utiliza para eliminar un valor de una tabla hash. Para borrar la Operación se hace usando el número de índice. Una vez que se ha eliminado un valor, el número de índice se libera. Puede usarse para almacenar otros valores usando la operación de inserción.

Implementación de tabla hash con ejemplo de Python

Veamos un ejemplo simple que calcula el valor hash de una clave.

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Explicación del código de la tabla hash

AQUÍ,

1. Define una función hash_key que acepta los parámetros key y m.
2. Utiliza una operación de módulo simple para determinar el valor hash
3. Define una variable m que se inicializa con el valor 7. Este es el tamaño de nuestra tabla hash
4. Calcula e imprime el valor hash de 3
5. Calcula e imprime el valor hash de 2
6. Calcula e imprime el valor hash de 9
7. Calcula e imprime el valor hash de 11
8. Calcula e imprime el valor hash de 7

La ejecución del código anterior produce los siguientes resultados.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Ejemplo de diccionario de Python

Python viene con un tipo de datos incorporado llamado Diccionario. Un diccionario es un ejemplo de tabla hash. Almacena valores usando un par de claves y valores. Los valores hash se generan automáticamente para nosotros y cualquier colisión se resuelve en segundo plano.

El siguiente ejemplo muestra cómo puede usar un tipo de datos de diccionario en Python 3

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

AQUÍ,

1. Define una variable de diccionario empleado. El nombre de la clave se utiliza para almacenar el valor John Doe, la edad almacena 36 y la posición almacena el valor Business Manager.
2. Recupera el valor del nombre de la clave y lo imprime en el terminal
3. Actualiza el valor de la posición clave al valor Ingeniero de software
4. Imprime los valores del nombre y la posición de las claves
5. Elimina todos los valores que están almacenados en nuestro diccionario variable empleado
6. Imprime el valor del empleado

La ejecución del código anterior produce los siguientes resultados.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Análisis de complejidad

Las tablas hash tienen una complejidad de tiempo promedio de O (1) en el mejor de los casos. La complejidad de tiempo en el peor de los casos es O (n). El peor de los casos ocurre cuando muchos valores generan la misma clave hash y tenemos que resolver la colisión probando.

Aplicaciones del mundo real

En el mundo real, las tablas hash se utilizan para almacenar datos para

• Bases de datos
• Matrices asociativas
• Conjuntos
• Memoria caché

Ventajas de las tablas hash

A continuación, se muestran las ventajas y los beneficios de usar tablas hash:

• Las tablas hash tienen un alto rendimiento al buscar datos, insertar y eliminar valores existentes.
• La complejidad temporal de las tablas hash es constante independientemente del número de elementos de la tabla.
• Funcionan muy bien incluso cuando trabajan con grandes conjuntos de datos.

Desventajas de las tablas hash

Aquí están las desventajas de usar tablas hash:

• No puede utilizar un valor nulo como clave.
• Las colisiones no se pueden evitar al generar claves usando. funciones hash. Las colisiones ocurren cuando se genera una clave que ya está en uso.
• Si la función hash tiene muchas colisiones, esto puede provocar una disminución del rendimiento.

Resumen:

• Las tablas hash se utilizan para almacenar datos mediante un par de claves y valores.
• Una función hash utiliza un algoritmo matemático para calcular el valor hash.
• Se produce una colisión cuando se genera el mismo valor hash para más de un valor.
• El encadenamiento resuelve la colisión mediante la creación de listas vinculadas.
• El sondeo resuelve la colisión al encontrar espacios vacíos en la tabla hash.
• El sondeo lineal busca la siguiente ranura libre para almacenar el valor a partir de la ranura donde ocurrió la colisión.
• El sondeo cuadrático usa expresiones polinomiales para encontrar el siguiente espacio libre cuando ocurre una colisión.
• El hash doble utiliza un algoritmo de función hash secundario para encontrar el siguiente espacio libre cuando ocurre una colisión.
• Las tablas hash tienen un mejor rendimiento en comparación con otras estructuras de datos.
• La complejidad de tiempo promedio de las tablas hash es O (1)
• Un tipo de datos de diccionario en Python es un ejemplo de una tabla hash.
• Las tablas hash admiten operaciones de inserción, búsqueda y eliminación.
• No se puede utilizar un valor nulo como valor de índice.
• Las colisiones no se pueden evitar en las funciones hash. Una buena función hash minimiza el número de colisiones que se producen para mejorar el rendimiento.