Tabla hash explicada: cómo funciona, código y complejidad

Qué problema resuelve una tabla hash

Imagina que guardas un millón de registros de usuarios y necesitas encontrar uno por su correo. Recorrer una lista es O(n). Mantenerla ordenada permite búsqueda binaria en O(log n), pero las inserciones se vuelven lentas. Una tabla hash encuentra el registro en O(1) promedio, sin importar cuántos registros haya, y insertar y eliminar son igual de rápidos.

Por eso las tablas hash están por todas partes: diccionarios y conjuntos en los lenguajes de programación, índices hash en bases de datos, cachés, tablas de símbolos en compiladores y deduplicación.

La idea en palabras sencillas

Imagina un guardarropa con 100 ganchos numerados. En lugar de revisar todos los ganchos para encontrar tu abrigo, el encargado calcula un número de gancho a partir de tu nombre y va directo a él. La función que calcula ese número es la función hash. Una buena función hash es rápida, siempre da el mismo número para la misma clave y reparte las claves distintas de forma uniforme entre los ganchos.

1. Calcula h = hash(key).
2. Elige el cubo: index = h % capacity.
3. Busca la clave solo en ese cubo.

Ejemplo resuelto: colisiones con encadenamiento

Toma una tabla con 4 cubos y una función hash de juguete: la suma de las posiciones de las letras (a = 1, b = 2, ...).

act y bee colisionan con cat. Ahora buscar bee implica revisar tres entradas del cubo 0. Con una función hash pobre (las sumas de letras ignoran el orden) o con muy pocos cubos, las cadenas crecen y la tabla se vuelve lenta. Las funciones hash reales mezclan todos los bits de la clave, y las tablas reales crecen cuando se llenan demasiado.

Implementación en Python con encadenamiento separado

Cada cubo es una lista de pares [key, value]. Cuando el número de elementos supera 0,75 veces el número de cubos (el factor de carga), la tabla duplica su capacidad y vuelve a insertar todo.

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

Comparación de estrategias de colisión

El dict de CPython usa direccionamiento abierto con una secuencia de sondeo perturbada y, desde Python 3.7, garantiza que la iteración siga el orden de inserción. El HashMap de Java usa encadenamiento y convierte las cadenas largas en árboles balanceados.

Complejidad temporal y espacial

El O(1) promedio depende de una buena función hash y de un factor de carga acotado. Python aleatoriza los hashes de las cadenas en cada proceso (hash seeding) para que un atacante no pueda enviar fácilmente muchas claves que colisionen y ralenticen un servidor a O(n) por petición.

Errores comunes

• Usar un objeto mutable como clave, o definir __eq__ en una clase sin el __hash__ correspondiente. Los objetos iguales deben tener hashes iguales.
• Esperar un orden. Una tabla hash da búsquedas rápidas, no orden; usa una lista ordenada o un árbol balanceado (un árbol binario de búsqueda) cuando necesites consultas por rango o la clave mínima.
• Confiar en los valores de hash() entre ejecuciones: los hashes de cadenas cambian entre procesos de Python salvo que se fije PYTHONHASHSEED. Usa hashlib para hashes estables.
• Tratar una tabla hash como una primitiva de seguridad. Las tablas hash usan hashes rápidos no criptográficos; las contraseñas necesitan funciones de hash de contraseñas específicas.

Cuándo usarla y usos típicos en entrevistas

Usa una tabla hash siempre que necesites responder rápido a "¿he visto esto antes?" o "¿qué valor corresponde a esta clave?". Usa un árbol binario de búsqueda o un arreglo ordenado cuando además necesites orden, rangos o las claves más cercanas.

Problemas clásicos: two sum (guarda el índice de cada número y busca target - x), contar frecuencias (collections.Counter), agrupar anagramas por letras ordenadas, detectar duplicados y memoizar resultados en programación dinámica.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)