Principios de funcionamiento de las tablas hash

6.1 Definición de tabla hash y su estructura

Tabla hash – es una estructura de datos que proporciona la capacidad de encontrar, insertar y eliminar elementos rápidamente utilizando una función hash para calcular índices en un array o lista. Las tablas hash son comúnmente usadas para implementar arrays asociativos, también conocidos como diccionarios.

Aspectos importantes de la tabla hash

Array – es el componente principal de una tabla hash, almacena punteros a elementos o listas de elementos.

Función hash: Una función que convierte claves de un diccionario en índices de un array.

Colisiones: Situación donde dos claves diferentes tienen el mismo valor hash. Para resolver colisiones se utilizan varios métodos, como chaining o direccionamiento abierto (open addressing).

Ejemplo de diccionario:

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

Ejemplo de estructura de tabla hash:

6.2 Operaciones principales en la tabla hash

Operaciones principales en la tabla hash: inserción, búsqueda, eliminación

1. Inserción (Insertion): El proceso de agregar un nuevo elemento (par clave-valor) en la tabla hash.

Pasos de inserción:

1. Calcular el valor hash de la clave usando la función hash.
2. Encontrar el índice en el array basado en el valor hash.
3. Si ya hay un elemento en ese índice del array (colisión), añadir el elemento en la lista (en caso de chaining) o encontrar el siguiente índice disponible (en caso de direccionamiento abierto).

Ejemplo de inserción en una tabla hash usando chaining:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

# Ejemplo de uso:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Búsqueda (Search): El proceso de encontrar un valor por una clave dada en la tabla hash.

Pasos de búsqueda:

1. Calcular el valor hash de la clave usando la función hash.
2. Encontrar el índice en el array basado en el valor hash.
3. Verificar la existencia de la clave en la lista de elementos (en caso de chaining) o por el índice (en caso de direccionamiento abierto).

Ejemplo de búsqueda en una tabla hash usando chaining:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# Ejemplo de uso:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Salida: 2
print(hash_table.search("grape"))   # Salida: None

3. Eliminación (Deletion): El proceso de eliminar un elemento (par clave-valor) de la tabla hash.

Pasos de eliminación:

1. Calcular el valor hash de la clave usando la función hash.
2. Encontrar el índice en el array basado en el valor hash.
3. Eliminar el elemento de la lista (en caso de chaining) o establecer el valor del índice en None (en caso de direccionamiento abierto).

Ejemplo de eliminación en una tabla hash usando chaining:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# Ejemplo de uso:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # Salida: None

6.3 Complejidad temporal de la tabla hash

Complejidad temporal de las operaciones en una tabla hash

Inserción (Insertion):

• Caso promedio: O(1)
• Peor caso: O(n) (en caso de un gran número de colisiones o si todos los elementos caen en el mismo lugar)

Búsqueda (Search):

• Caso promedio: O(1)
• Peor caso: O(n) (en caso de un gran número de colisiones o si todos los elementos caen en el mismo lugar)

Eliminación (Deletion):

• Caso promedio: O(1)
• Peor caso: O(n) (en caso de un gran número de colisiones o si todos los elementos caen en el mismo lugar)

Explicación:

Caso promedio: En el caso promedio, la función hash distribuye uniformemente los elementos en la tabla, y cada elemento se encuentra en su celda única, lo que asegura un tiempo de acceso constante O(1).

Peor caso: En el peor caso, todos los elementos caen en una sola celda debido a una mala función hash o a un gran número de colisiones. Entonces, la tabla hash se convierte en una lista enlazada, y la complejidad temporal de las operaciones se vuelve O(n).

6.4 Ejemplos de uso de tablas hash

1. Implementación de diccionario (array asociativo)

Las tablas hash se utilizan a menudo para implementar diccionarios, que permiten almacenar pares clave-valor y proporcionan acceso rápido mediante la clave.

Ejemplo:

# Creación de un diccionario
dictionary = {}

# Inserción de elementos
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Búsqueda de un elemento
print(dictionary["banana"])  # Salida: 2

# Eliminación de un elemento
del dictionary["cherry"]

# Verificación de la existencia de una clave
if "apple" in dictionary:
    print("La clave 'apple' existe en el diccionario")  # Salida: La clave 'apple' existe en el diccionario

Ahora sabes un poco más sobre el diccionario en Python y cómo está estructurado.

2. Cachear resultados de cálculos

Las tablas hash se utilizan para cachear los resultados de cálculos costosos para acelerar solicitudes posteriores.

Ejemplo:

# Caché para almacenar resultados
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Ejemplo de cálculo costoso
    cache[x] = result
    return result

# Uso de la caché
print(expensive_computation(10))  # Salida: 100 (cálculo y cacheo)
print(expensive_computation(10))  # Salida: 100 (desde la caché)

3. Contar la frecuencia de palabras en un texto

Las tablas hash se utilizan para contar el número de ocurrencias de cada palabra en un texto.

Ejemplo:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# Salida de resultados
for word, count in word_count.items():
    print(f"La palabra '{word}' aparece {count} vez/veces")

4. Búsqueda de duplicados en una lista

Las tablas hash se utilizan para la búsqueda eficiente de duplicados en una lista.

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Ejemplo de uso
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Salida: [2, 4]