3 - Tabla hash en C (vision general)

Estructura base

Una tabla hash usa un array como almacenamiento principal y una funcion hash para traducir la clave en un indice. Cada posicion del array es un bucket que puede guardar un elemento o una estructura auxiliar si hay colisiones.

3.1 Representacion basica con arrays

#include <stdlib.h>

typedef struct {
  const char *clave;
  int valor;
  int ocupado; /* 0 = libre, 1 = ocupado */
} Entrada;

typedef struct {
  Entrada *buckets;
  unsigned long capacidad;
  unsigned long cantidad;
} TablaHash;

TablaHash *tabla_crear(unsigned long capacidad) {
  TablaHash *t = malloc(sizeof(TablaHash));
  t->capacidad = capacidad;
  t->cantidad = 0;
  t->buckets = calloc(capacidad, sizeof(Entrada));
  return t;
}

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

3.2 Clave → indice

La clave se transforma con la funcion hash en un entero, y el modulo de la capacidad define el bucket:

unsigned long indice = hash_cadena(clave) % tabla->capacidad;

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

3.3 Tamano de la tabla

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

3.4 Carga de la tabla (load factor)

El factor de carga alpha es la relacion entre elementos guardados y capacidad total:

double alpha = (double)tabla->cantidad / (double)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 mas grande y reinsertar cada elemento calculando de nuevo su indice. Flujo basico:

  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 funcion hash.
  4. Liberar el array viejo y actualizar los punteros.

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

3.6 Comparacion con arboles y listas

  • Vs. arboles balanceados: las tablas hash logran O(1) promedio frente a O(log n) de los arboles, pero pierden ordenamiento y requieren funcion hash.
  • Vs. listas enlazadas: las listas tienen insercion constante sin rehash, pero busqueda O(n); la tabla hash mejora la busqueda a costa de memoria extra.
  • Orden: ni las tablas hash ni las listas brindan orden natural; los arboles si pueden mantenerlo.
  • Memoria: las tablas hash reservan espacio por adelantado; las listas y arboles crecen nodo a nodo.
Retornar