Tabla hash en estructura de datos: Python Ejemplo

¿Qué es Hashing?

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.

¿Qué es una tabla hash?

A TABLA DE PICADILLO es una estructura de datos que almacena valores utilizando 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 de la cantidad de elementos que contenga.

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 utilizar 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 usará para hacer referencia al valor que queremos almacenar. La función acepta el valor que se 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 para nuestra función hash, donde k1 es el valor que queremos almacenar y m es el tamaño de la lista. Usamos el operador 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 debe ocupar cada valor.

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

Paso 1) Calcula la posición que ocupará el primer valor así.

h(1) = 1 % 3

= 1

El valor 1 ocupará el espacio en Índice 1

Paso 2) Calcular la posición que ocupará el segundo valor.

h(2) = 2 % 3

= 2

El valor 2 ocupará el espacio en Í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 Índice 0

Resultado final de

Nuestra tabla hash completada 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 datos de entrada que tengan la misma cantidad.
• La función debe 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 hashes 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.

Clave	Algoritmo hash (k1 % 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 planteado se puede resolver mediante encadenamiento o sondeo. En las siguientes secciones se analizan en detalle el encadenamiento y el sondeo.

Encadenamiento

El encadenamiento es una técnica que se utiliza para resolver el problema de 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 utiliza 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 colisiones es el sondeo. Cuando utilizamos 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 ranuras vacías 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 polinómicas cuadráticas para encontrar el siguiente espacio libre disponible.
Double Hashing	Esta técnica utiliza un algoritmo de función hash secundaria para encontrar la siguiente ranura 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

Aquí están los Operaciones soportadas por tablas Hash:

• Inserción - Este OperaLa ción se utiliza para agregar un elemento a la tabla hash.
• Búsqueda - Este Operación se utiliza para buscar elementos en la tabla hash usando la clave
• Eliminación - Este OperaLa ción se utiliza para eliminar elementos de la tabla hash.

Operación de inserció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 mediante 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 operaciones 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 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 número de índice 2 devolverá el valor 6.

Operación de eliminación de datos

La operación de eliminación se utiliza para eliminar un valor de una tabla hash. Para eliminar el valor OperaLa eliminación se realiza mediante el número de índice. Una vez que se ha eliminado un valor, el número de índice queda libre. Se puede utilizar para almacenar otros valores mediante la operación de inserción.

Implementación de tabla hash con Python Ejemplo

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

def hash_key( key, m):
    return key % m


m = 7

print(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 clave 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 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

Python Ejemplo de diccionario

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

El siguiente ejemplo muestra cómo se puede utilizar 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 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 la terminal.
3. Actualiza el valor de la posición clave al valor Ingeniero de software
4. Imprime los valores del nombre y 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 temporal promedio de O (1) en el mejor de los casos. La complejidad temporal 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 mediante un sondeo.

Aplicaciones del mundo real

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

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

Ventajas de las tablas hash

A continuación se detallan las ventajas y ventajas de utilizar 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

Estas son las desventajas de usar tablas hash:

• No puede utilizar un valor nulo como clave.
• No se pueden evitar colisiones al generar claves utilizando. 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 utilizando 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 utiliza expresiones polinómicas para encontrar el siguiente espacio libre cuando ocurre una colisión.
• Double El hashing utiliza un algoritmo de función hash secundaria para encontrar la siguiente ranura libre cuando ocurre una colisión.
• Las tablas hash tienen un mejor rendimiento en comparación con otras estructuras de datos.
• La complejidad temporal promedio de las tablas hash es O (1)
• Un tipo de datos de diccionario en Python es un ejemplo de tabla hash.
• Las tablas hash admiten operaciones de inserción, búsqueda y eliminación.
• Un valor nulo no se puede utilizar como valor de índice.
• Las colisiones no se pueden evitar en las funciones hash. Una buena función hash minimiza la cantidad de colisiones que ocurren para mejorar el rendimiento.