5.3 Hashing y Tablas Hash

El hashing es una técnica fundamental utilizada en informática para acceder rápidamente a datos almacenados en memoria. Se basa en un concepto simple pero poderoso: mapear datos a una ubicación específica en memoria para que puedan recuperarse rápida y eficientemente. La idea clave detrás del hashing es utilizar una función hash que convierta los datos de entrada, también llamados 'clave', en un índice único que corresponde a la ubicación de memoria donde se almacenan los datos. Esto significa que una vez que los datos están hasheados y almacenados, pueden recuperarse al instante utilizando la misma función hash para calcular su índice.

Una función hash es una función matemática que toma una entrada, generalmente una cadena o un número, y devuelve una salida de tamaño fijo, que es el valor hash. El valor hash se utiliza luego como un índice para acceder a los datos en memoria. La función hash ideal debería distribuir los datos de manera uniforme en la memoria para evitar colisiones, que ocurren cuando dos claves se asignan al mismo índice. Sin embargo, encontrar la función hash perfecta es una tarea desafiante, y se utilizan diferentes técnicas como encadenamiento o direccionamiento abierto para manejar las colisiones.

El encadenamiento es una técnica que implica almacenar múltiples valores en el mismo índice, formando una lista enlazada. Cuando ocurre una colisión, el nuevo valor se agrega al final de la lista enlazada. Por otro lado, el direccionamiento abierto implica encontrar el siguiente índice disponible cuando ocurre una colisión. Esto se puede hacer utilizando diferentes algoritmos como sondeo lineal o sondeo cuadrático.

En resumen, el hashing es una técnica poderosa que permite la recuperación eficiente de datos en informática. Se basa en la idea de utilizar una función hash para mapear datos a una ubicación específica en memoria, y se utilizan diferentes técnicas para manejar las colisiones. Al comprender el hashing y sus aplicaciones, los programadores pueden desarrollar software más rápido y eficiente que pueda procesar grandes cantidades de datos en tiempo real.

Una Tabla Hash es un concepto fundamental en informática y es una estructura de datos comúnmente utilizada para almacenar y recuperar datos. Es una herramienta poderosa que permite un acceso rápido y eficiente a los datos mediante un proceso llamado hashing. El hashing implica convertir el valor clave de los datos en un índice o dirección de una matriz de compartimentos o slots donde se almacena el valor. Esto significa que los datos pueden ser fácilmente accedidos y recuperados sin tener que buscar a través de todo el conjunto de datos.

Uno de los beneficios de usar una Tabla Hash es la capacidad de almacenar pares clave-valor, lo cual es útil en muchas aplicaciones. Por ejemplo, una Tabla Hash puede usarse para almacenar información sobre una persona, con el nombre de la persona como clave y la información asociada como su dirección, número de teléfono y dirección de correo electrónico como el valor. Esto permite un acceso rápido y fácil a la información de la persona simplemente buscando su nombre.

Otro beneficio de las Tablas Hash es su capacidad para manejar grandes cantidades de datos. Debido a que las Tablas Hash usan una función hash para calcular un índice en una matriz de compartimentos o slots, incluso los conjuntos de datos grandes pueden ser almacenados y accedidos eficientemente. Además, las Tablas Hash también pueden ser redimensionadas dinámicamente, lo que significa que pueden crecer o disminuir según sea necesario para acomodar la cantidad de datos que se están almacenando.

En general, la Tabla Hash es una herramienta esencial en informática y se utiliza en una amplia variedad de aplicaciones. Ya sea que estés trabajando con un conjunto de datos pequeño o grande, una Tabla Hash puede ayudarte a almacenar y recuperar datos rápida y eficientemente.

Aquí tienes un ejemplo de una función hash básica y una tabla hash simple en Python:

# Define a simple hash function
def simple_hash(key):
    return key % 10

# Initialize a hash table as a list with 10 elements
hash_table = [None] * 10

# Let's add some data
key = 35
value = "Apple"

# Compute the index
index = simple_hash(key)

# Store the value in the hash table
hash_table[index] = value

print(hash_table)

Esto producirá:

[None, None, None, None, None, 'Apple', None, None, None, None]

En este caso, hemos utilizado la función hash simple key % 10 para determinar dónde almacenar nuestro valor, "Apple". La clave es 35, y 35 % 10 es igual a 5, por lo que "Apple" se almacena en el índice 5.

Sin embargo, ten en cuenta que este es un ejemplo muy básico con fines ilustrativos. En la práctica, las funciones hash pueden ser mucho más complejas, y las tablas hash incluirán métodos para manejar colisiones, así como métodos para agregar, eliminar y recuperar datos.

Recuerda que la eficiencia de una tabla hash depende en gran medida de la función hash y del factor de carga (la relación entre el número de elementos y el número de slots). Si está bien implementada, una tabla hash puede proporcionar una complejidad temporal de O(1) para las operaciones de búsqueda, inserción y eliminación.

Las tablas hash encuentran su uso en una multitud de aplicaciones, como la indexación de bases de datos, el almacenamiento en caché, el almacenamiento de contraseñas y mucho más. La capacidad de acceder rápidamente a los datos a través de una clave las hace increíblemente útiles en situaciones donde el acceso rápido es crítico.

5.3.1 Colisiones

Las colisiones son un fenómeno común en las funciones hash, que pueden ocurrir cuando dos entradas diferentes se asignan al mismo valor de salida. Aunque se supone que las funciones hash son deterministas, devolviendo la misma salida para la misma entrada, las colisiones pueden causar problemas.

Para lidiar con estas colisiones, se emplean varios métodos, como el encadenamiento, el direccionamiento abierto y el doble hash. El encadenamiento implica almacenar los valores en conflicto en el mismo índice, mientras que el direccionamiento abierto implica buscar el siguiente índice disponible para almacenar el valor.

El doble hash es un método más complejo que utiliza dos funciones hash para resolver colisiones. Al comprender los diferentes métodos de resolución de colisiones, es posible crear funciones hash más eficientes y efectivas para una amplia gama de aplicaciones.

Hay varias estrategias para resolver estas colisiones:

Encadenamiento

El encadenamiento es una técnica utilizada en las tablas hash donde cada índice en la tabla es en realidad un array de listas enlazadas, y cada lista enlazada contiene todas las claves cuyos valores hash se asignan a ese índice. Cuando ocurre una colisión, el par clave-valor simplemente se agrega al final de la lista en el índice en conflicto.

Este método proporciona un mecanismo para manejar colisiones de manera más eficiente mientras se conserva el rendimiento constante de las búsquedas en la tabla hash. Para buscar un valor, primero hashearías la clave para encontrar el índice y luego recorrerías la lista enlazada en ese índice hasta que encuentres el valor deseado. Este enfoque tiene la ventaja de ser fácil de implementar y tener un rendimiento predecible en el peor de los casos, lo que lo convierte en una opción popular para las implementaciones de tablas hash.

Aquí tienes un ejemplo:

# An example of a hash table using chaining in Python
hash_table = [[] for _ in range(10)]

def insert(hash_table, key, value):
    hash_key = hash(key) % len(hash_table)
    key_exists = False
    bucket = hash_table[hash_key]
    for i, kv in enumerate(bucket):
        k, v = kv
        if key == k:
            key_exists = True
            break
    if key_exists:
        bucket[i] = ((key, value))
    else:
        bucket.append((key, value))

# Insert some values
insert(hash_table, 10, 'Apple')
insert(hash_table, 25, 'Banana')
insert(hash_table, 20, 'Cherry')

En este caso, tanto las claves 10 y 20 se hashan al mismo índice (0), pero las colisiones se manejan agregando el nuevo par clave-valor al final de la lista en ese índice.

Direccionamiento Abierto

El direccionamiento abierto es uno de los métodos utilizados para la implementación de tablas hash. En este método, todos los pares clave-valor se almacenan en la propia tabla hash. Cuando ocurre una colisión, la función hash busca el siguiente espacio disponible en la tabla. Hay varias formas de encontrar el siguiente espacio vacío, llamadas secuencias de sondeo.

Una de esas secuencias es el sondeo lineal, donde la función hash verifica secuencialmente cada espacio en el array hasta que encuentra uno vacío. Otra secuencia es el sondeo cuadrático, donde la función hash verifica los espacios tomando saltos de tamaño creciente. Por último, el doble hash es otra secuencia de sondeo donde la función hash utiliza una segunda función hash para definir la secuencia de sondeos.

Este método puede ser más lento que el encadenamiento, pero puede proporcionar un mejor rendimiento en ciertos casos de uso.

Aquí tienes un ejemplo:

# An example of a hash table using linear probing in Python
hash_table = [None] * 10

def insert(hash_table, key, value):
    hash_key = hash(key) % len(hash_table)
    while hash_table[hash_key] is not None:
        hash_key = (hash_key + 1) % len(hash_table)
    hash_table[hash_key] = value

# Insert some values
insert(hash_table, 10, 'Apple')
insert(hash_table, 25, 'Banana')
insert(hash_table, 20, 'Cherry')

En este caso, si dos claves se hashan al mismo índice, la segunda clave se coloca en el siguiente espacio disponible.

Aunque la creación de funciones hash y tablas hash puede parecer sencilla al principio, en realidad ocultan mucha complejidad bajo la superficie. Sin embargo, comprender estas estructuras de datos es crucial para todo programador, ya que son una forma eficiente de manejar y acceder a los datos. En la siguiente sección, profundizaremos en nuestra comprensión a través de algunos problemas prácticos.

Uno de los aspectos más cruciales de implementar una tabla hash es seleccionar una función hash adecuada. Para asegurarse de que la tabla hash funcione eficientemente, la función hash debe ser elegida cuidadosamente para distribuir las claves de manera uniforme a lo largo del array.

Esto se hace para evitar o minimizar las colisiones, que pueden ralentizar el rendimiento de la tabla hash. Además, la selección de la función hash depende del tipo de datos almacenados en la tabla hash.

Por ejemplo, si los datos almacenados en la tabla hash son de un tipo particular, entonces se puede usar una función hash específica para optimizar el rendimiento de la tabla hash. Por lo tanto, seleccionar la función hash apropiada es un paso crítico en la implementación de una tabla hash. Una buena función hash cumple con los siguientes criterios:

Una buena función hash tiene las siguientes características:
Determinista: Dada una entrada particular, la salida (valor hash) siempre será la misma. Esto garantiza consistencia y previsibilidad.
Rápido para calcular el valor hash: Es importante que una función hash sea capaz de devolver el valor hash rápidamente para cualquier entrada dada para optimizar el rendimiento.
Distribución uniforme: La función hash debe distribuir las claves de manera uniforme a lo largo del array. Esto significa que cada índice en el array debería tener la misma probabilidad, evitando la agrupación de valores en una región específica. Una distribución uniforme ayuda a evitar colisiones, lo que puede disminuir la eficiencia de la tabla hash y ralentizar el tiempo de búsqueda.
Menos propenso a causar colisiones: Aunque las colisiones son inevitables, una buena función hash tiene como objetivo minimizarlas tanto como sea posible. Una tasa baja de colisiones garantiza que la tabla hash siga siendo eficiente y no sufra de degradación de rendimiento debido a colisiones excesivas.
Robustez: Una función hash robusta puede manejar una amplia gama de datos de entrada y producir un valor hash único para cada entrada. Esto es importante para garantizar que la tabla hash pueda manejar una variedad de tipos y tamaños de datos, sin comprometer el rendimiento o la eficiencia.
Seguridad: En algunos casos, es importante que la función hash sea segura y resistente a ataques. Por ejemplo, en criptografía, las funciones hash se utilizan para garantizar la integridad de los datos y prevenir manipulaciones. Una función hash segura debe estar diseñada para resistir ataques como colisiones, ataques de preimagen y ataques de cumpleaños, entre otros.

Aquí tienes un ejemplo de implementación de una función hash simple:

def hash_function(key):
    return key % 10

En este ejemplo, la función hash es simplemente el residuo de dividir la clave por el tamaño del array (en este caso, 10). Es muy rápido y fácil de calcular, pero puede que no distribuya las claves de manera uniforme, especialmente si las claves tienen algunos patrones regulares.

Ten en cuenta que estos principios son solo lo básico. El campo del hashing es un área profunda y activa de investigación en informática, y los cursos avanzados cubrirán tipos más complejos de funciones hash, estrategias de resolución de colisiones y sus aplicaciones.

La belleza de las tablas hash es que nos permiten mantener una asociación entre claves y valores, similar a lo que tendríamos en un diccionario o un mapa, y lo hacen de una manera que permite búsquedas, adiciones y eliminaciones de entradas muy rápidas (idealmente en tiempo constante).