3 - Tabla hash en Python (visión general)

Estructura base

Una tabla hash usa un array como almacenamiento principal y una función hash para traducir la clave en un índice. Cada posición del array es un bucket que puede guardar un elemento o una estructura auxiliar si hay colisiones.

3.1 Representación básica con arrays

class Entrada:
  def __init__(self, clave=None, valor=None):
    self.clave = clave
    self.valor = valor
    self.ocupado = clave is not None

class TablaHash:
  def __init__(self, capacidad):
    self.capacidad = capacidad
    self.cantidad = 0
    self.buckets = [Entrada() for _ in range(capacidad)]

El array buckets guarda entradas en una lista contigua, lo que facilita indexar y recorrer cuando se rehash.

3.2 Clave e índice

La clave se transforma con la función hash en un entero, y el módulo de la capacidad define el bucket:

indice = hash_cadena(clave) % tabla.capacidad

Ese índice apunta al bucket donde se intenta insertar o buscar. Si el bucket está ocupado por otra clave, se aplica la estrategia de colisiones (que detallaremos en temas posteriores).

3.3 Tamaño de la tabla

El tamaño inicial (capacidad) suele elegirse como potencia de dos o número primo para mejorar la dispersión. Tablas muy pequeñas generan colisiones inmediatas; tablas enormes desperdician memoria. Lo habitual es comenzar con 8, 16 o 32 buckets y crecer según el uso.

3.4 Carga de la tabla (load factor)

El factor de carga alpha es la relación entre elementos guardados y capacidad total:

alpha = tabla.cantidad / tabla.capacidad

Valores comunes de referencia:

  • alpha <= 0.5: pocas colisiones, espacio holgado.
  • 0.5 < alpha <= 0.75: equilibrio entre memoria y rendimiento.
  • alpha > 0.75: comienzan a crecer las colisiones; conviene rehash.

3.5 Redimensionamiento (rehashing)

Rehashing significa crear un nuevo array más grande y reinsertar cada elemento calculando de nuevo su índice. Flujo básico:

  1. Calcular nueva capacidad (por ejemplo, duplicar la actual).
  2. Reservar un array limpio de buckets.
  3. Recorrer la tabla anterior y reinsertar cada par clave-valor con la misma función hash.
  4. Liberar la lista vieja y actualizar las referencias.

Este proceso mantiene la complejidad amortizada O(1), aunque cada rehash puntual cuesta O(n) porque se mueven todos los elementos.

3.6 Comparación con árboles y listas

  • Vs. árboles balanceados: las tablas hash logran O(1) promedio frente a O(log n) de los árboles, pero pierden ordenamiento y requieren función hash.
  • Vs. listas enlazadas: las listas tienen inserción constante sin rehash, pero búsqueda O(n); la tabla hash mejora la búsqueda a costa de memoria extra.
  • Orden: ni las tablas hash ni las listas brindan orden natural; los árboles sí pueden mantenerlo.
  • Memoria: las tablas hash reservan espacio por adelantado; las listas y árboles crecen nodo a nodo.
Retornar