8 - Rehash en Encadenamiento (Separate Chaining)

Por que y cuando rehash

En encadenamiento, el factor de carga alpha = cantidad / capacidad indica cuantas claves en promedio hay por bucket. Al crecer alpha aumentan las colisiones y las listas por bucket se alargan. Un rehash crea una tabla mas grande y reubica cada nodo, recuperando el tiempo promedio O(1).

8.1 Umbral de rehash

  • Sugerido: iniciar rehash cuando alpha >= 1.0 (una colision promedio por bucket).
  • Aplicaciones exigentes: rehash en 0.75 si buscas colas de listas cortas y latencia estable.
  • Con pocas eliminaciones: puedes tolerar alpha mayor, pero mide la longitud maxima de listas.

8.2 Pasos del rehash

  1. Elegir nueva capacidad (por ejemplo, doblar y usar el siguiente impar/primo).
  2. Crear un nuevo array de buckets inicializados en NULL.
  3. Recorrer todos los buckets antiguos y reinsertar cada nodo en la nueva tabla usando la misma funcion hash.
  4. Actualizar los campos de la tabla para apuntar a los nuevos buckets y la nueva capacidad.

8.3 Codigo en C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HashNode {
  const char *clave;
  int valor;
  struct HashNode *sig;
} HashNode;

typedef struct {
  HashNode **buckets;
  unsigned long capacidad;
  unsigned long cantidad;
} HashTable;

static unsigned long hash_cadena(const char *clave, unsigned long cap) {
  unsigned long h = 5381;
  int c;
  while ((c = *clave++) != 0) {
    h = ((h << 5) + h) + (unsigned long)c; /* djb2 */
  }
  return h % cap;
}

HashTable *hash_crear(unsigned long capacidad) {
  HashTable *t = malloc(sizeof(HashTable));
  if (!t) return NULL;
  t->capacidad = capacidad;
  t->cantidad = 0;
  t->buckets = calloc(capacidad, sizeof(HashNode *));
  return t;
}

int hash_insertar(HashTable *t, const char *clave, int valor) {
  unsigned long idx = hash_cadena(clave, t->capacidad);
  HashNode *nodo = t->buckets[idx];
  while (nodo != NULL) {
    if (strcmp(nodo->clave, clave) == 0) {
      nodo->valor = valor;
      return 1;
    }
    nodo = nodo->sig;
  }
  HashNode *nuevo = malloc(sizeof(HashNode));
  if (!nuevo) return 0;
  nuevo->clave = clave;
  nuevo->valor = valor;
  nuevo->sig = t->buckets[idx];
  t->buckets[idx] = nuevo;
  t->cantidad++;
  return 1;
}

static int hash_reinsertar(HashTable *destino, const char *clave, int valor) {
  unsigned long idx = hash_cadena(clave, destino->capacidad);
  HashNode *nuevo = malloc(sizeof(HashNode));
  if (!nuevo) return 0;
  nuevo->clave = clave;
  nuevo->valor = valor;
  nuevo->sig = destino->buckets[idx];
  destino->buckets[idx] = nuevo;
  destino->cantidad++;
  return 1;
}

int hash_rehash(HashTable *t, unsigned long nueva_capacidad) {
  HashNode **nuevos_buckets = calloc(nueva_capacidad, sizeof(HashNode *));
  if (!nuevos_buckets) return 0;

  HashTable destino = { nuevos_buckets, nueva_capacidad, 0 };

  for (unsigned long i = 0; i < t->capacidad; i++) {
    HashNode *n = t->buckets[i];
    while (n != NULL) {
      HashNode *sig = n->sig;
      if (!hash_reinsertar(&destino, n->clave, n->valor)) {
        /* en caso de fallo, liberar lo nuevo */
        for (unsigned long j = 0; j < destino.capacidad; j++) {
          HashNode *p = destino.buckets[j];
          while (p) {
            HashNode *tmp = p->sig;
            free(p);
            p = tmp;
          }
        }
        free(nuevos_buckets);
        return 0;
      }
      free(n);
      n = sig;
    }
  }

  free(t->buckets);
  t->buckets = nuevos_buckets;
  t->capacidad = nueva_capacidad;
  t->cantidad = destino.cantidad;
  return 1;
}

Nota: se libera cada nodo antiguo tras reinsertarlo. Si las claves provienen de strings dinamicos, asegúrate de decidir si se copian o se comparten.

8.4 Programa completo para probar en CLion

Ejemplo autocontenido que dispara rehash cuando alpha supera 1.0. Copia este archivo como main.c en un proyecto de consola de CLion para ver el crecimiento y la redistribucion de buckets.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HashNode {
  const char *clave;
  int valor;
  struct HashNode *sig;
} HashNode;

typedef struct {
  HashNode **buckets;
  unsigned long capacidad;
  unsigned long cantidad;
} HashTable;

static unsigned long hash_cadena(const char *clave, unsigned long cap) {
  unsigned long h = 5381;
  int c;
  while ((c = *clave++) != 0) {
    h = ((h << 5) + h) + (unsigned long)c; /* djb2 */
  }
  return h % cap;
}

HashTable *hash_crear(unsigned long capacidad) {
  HashTable *t = malloc(sizeof(HashTable));
  if (!t) return NULL;
  t->capacidad = capacidad;
  t->cantidad = 0;
  t->buckets = calloc(capacidad, sizeof(HashNode *));
  return t;
}

int hash_insertar(HashTable *t, const char *clave, int valor) {
  unsigned long idx = hash_cadena(clave, t->capacidad);
  HashNode *nodo = t->buckets[idx];
  while (nodo != NULL) {
    if (strcmp(nodo->clave, clave) == 0) {
      nodo->valor = valor;
      return 1;
    }
    nodo = nodo->sig;
  }
  HashNode *nuevo = malloc(sizeof(HashNode));
  if (!nuevo) return 0;
  nuevo->clave = clave;
  nuevo->valor = valor;
  nuevo->sig = t->buckets[idx];
  t->buckets[idx] = nuevo;
  t->cantidad++;
  return 1;
}

static int hash_reinsertar(HashTable *destino, const char *clave, int valor) {
  unsigned long idx = hash_cadena(clave, destino->capacidad);
  HashNode *nuevo = malloc(sizeof(HashNode));
  if (!nuevo) return 0;
  nuevo->clave = clave;
  nuevo->valor = valor;
  nuevo->sig = destino->buckets[idx];
  destino->buckets[idx] = nuevo;
  destino->cantidad++;
  return 1;
}

int hash_rehash(HashTable *t, unsigned long nueva_capacidad) {
  HashNode **nuevos_buckets = calloc(nueva_capacidad, sizeof(HashNode *));
  if (!nuevos_buckets) return 0;
  HashTable destino = { nuevos_buckets, nueva_capacidad, 0 };

  for (unsigned long i = 0; i < t->capacidad; i++) {
    HashNode *n = t->buckets[i];
    while (n != NULL) {
      HashNode *sig = n->sig;
      if (!hash_reinsertar(&destino, n->clave, n->valor)) {
        for (unsigned long j = 0; j < destino.capacidad; j++) {
          HashNode *p = destino.buckets[j];
          while (p) {
            HashNode *tmp = p->sig;
            free(p);
            p = tmp;
          }
        }
        free(nuevos_buckets);
        return 0;
      }
      free(n);
      n = sig;
    }
  }

  free(t->buckets);
  t->buckets = nuevos_buckets;
  t->capacidad = nueva_capacidad;
  t->cantidad = destino.cantidad;
  return 1;
}

void hash_destruir(HashTable *t) {
  for (unsigned long i = 0; i < t->capacidad; i++) {
    HashNode *n = t->buckets[i];
    while (n) {
      HashNode *tmp = n->sig;
      free(n);
      n = tmp;
    }
  }
  free(t->buckets);
  free(t);
}

int main(void) {
  HashTable *tabla = hash_crear(4);
  const char *claves[] = { "juan", "ana", "luis", "pedro", "maria", "sofia" };
  int valores[] = { 50, 23, 19, 90, 41, 77 };
  size_t n = sizeof(claves) / sizeof(claves[0]);

  for (size_t i = 0; i < n; i++) {
    double alpha = (double)(tabla->cantidad + 1) / (double)tabla->capacidad;
    if (alpha >= 1.0) {
      unsigned long nueva = tabla->capacidad * 2 + 1; /* siguiente impar */
      printf("Rehash a capacidad %lu (alpha previsto %.2f)\n", nueva, alpha);
      hash_rehash(tabla, nueva);
    }
    hash_insertar(tabla, claves[i], valores[i]);
  }

  printf("Tabla final:\n");
  for (unsigned long i = 0; i < tabla->capacidad; i++) {
    printf("[%lu]: ", i);
    HashNode *nodo = tabla->buckets[i];
    while (nodo) {
      printf("(%s -> %d) ", nodo->clave, nodo->valor);
      nodo = nodo->sig;
    }
    printf("\n");
  }

  hash_rehash(tabla, tabla->capacidad * 2 + 1);
  printf("Tras rehash manual:\n");
  for (unsigned long i = 0; i < tabla->capacidad; i++) {
    printf("[%lu]: ", i);
    HashNode *nodo = tabla->buckets[i];
    while (nodo) {
      printf("(%s -> %d) ", nodo->clave, nodo->valor);
      nodo = nodo->sig;
    }
    printf("\n");
  }

  hash_destruir(tabla);
  return 0;
}

Ejecutalo en tu proyecto de consola y observa como la capacidad crece antes de que el factor de carga supere 1.0.

Animacion: rehash con encadenamiento

Inserta juan, ana, luis, pedro, maria y sofia en una tabla que rehash al superar alpha 1.0. Se duplican buckets (capacidad * 2 + 1) y se reinsertan todos los nodos.

Tabla vacia (capacidad 4), factor de carga objetivo 1.0.
Capacidad inicial: 4 Rehash: cap = cap * 2 + 1 alpha limite: 1.0 Insercion al frente en cada bucket (chaining).
Retornar