9 - Rehash en direccionamiento abierto

Mantener alpha bajo en open addressing

En direccionamiento abierto, el factor de carga alpha = n / m controla la longitud de las sondas. Si alpha crece, las sondas se alargan y el rendimiento cae; rehashing agranda la tabla y reinserta las claves con la misma secuencia de probing.

9.1 Umbral y capacidad

  • Umbral sugerido: rehash cuando alpha alcance 0.65-0.75.
  • Capacidad: usar numeros primos ayuda a recorrer toda la tabla con doble hashing.
  • Paso: h2 = 1 + (h % (cap - 1)) mantiene el paso coprimo con la capacidad.

9.2 Pasos del rehash en open addressing

  1. Elegir una nueva capacidad (por ejemplo, cap * 2 + 1 y ajustar al siguiente primo).
  2. Crear un nuevo array de entradas marcadas como vacias.
  3. Recorrer la tabla vieja y reinsertar cada entrada ocupada con la secuencia de probing.
  4. Reemplazar la tabla vieja y actualizar la capacidad y la cantidad.

9.3 Codigo base con rehash

typedef enum { CELDA_VACIA, CELDA_OCUPADA, CELDA_BORRADA } Estado;

typedef struct {
  const char *clave;
  int valor;
  Estado estado;
} Entrada;

typedef struct {
  Entrada *celdas;
  unsigned long capacidad;
  unsigned long cantidad;
} HashOA;

static unsigned long hash1(const char *clave, unsigned long cap);
static unsigned long hash2(const char *clave, unsigned long cap);

static int insertar_sin_rehash(HashOA *t, const char *clave, int valor) {
  unsigned long base = hash1(clave, t->capacidad);
  unsigned long paso = hash2(clave, t->capacidad);
  long primera_borrada = -1;
  for (unsigned long i = 0; i < t->capacidad; i++) {
    unsigned long idx = (base + i * paso) % t->capacidad;
    if (t->celdas[idx].estado == CELDA_OCUPADA && strcmp(t->celdas[idx].clave, clave) == 0) {
      t->celdas[idx].valor = valor;
      return 1;
    }
    if (t->celdas[idx].estado == CELDA_BORRADA && primera_borrada == -1) primera_borrada = (long)idx;
    if (t->celdas[idx].estado == CELDA_VACIA) {
      unsigned long destino = (primera_borrada != -1) ? (unsigned long)primera_borrada : idx;
      t->celdas[destino].clave = clave;
      t->celdas[destino].valor = valor;
      t->celdas[destino].estado = CELDA_OCUPADA;
      t->cantidad++;
      return 1;
    }
  }
  return 0;
}

int hash_oa_rehash(HashOA *t, unsigned long nueva_capacidad) {
  Entrada *nuevas = malloc(sizeof(Entrada) * nueva_capacidad);
  if (!nuevas) return 0;
  for (unsigned long i = 0; i < nueva_capacidad; i++) {
    nuevas[i].estado = CELDA_VACIA;
    nuevas[i].clave = NULL;
    nuevas[i].valor = 0;
  }

  Entrada *viejas = t->celdas;
  unsigned long vieja_cap = t->capacidad;
  t->celdas = nuevas;
  t->capacidad = nueva_capacidad;
  t->cantidad = 0;

  for (unsigned long i = 0; i < vieja_cap; i++) {
    if (viejas[i].estado == CELDA_OCUPADA) {
      insertar_sin_rehash(t, viejas[i].clave, viejas[i].valor);
    }
  }

  free(viejas);
  return 1;
}

9.4 Programa completo para probar en CLion

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

typedef enum { CELDA_VACIA, CELDA_OCUPADA, CELDA_BORRADA } Estado;

typedef struct {
  const char *clave;
  int valor;
  Estado estado;
} Entrada;

typedef struct {
  Entrada *celdas;
  unsigned long capacidad;
  unsigned long cantidad;
} HashOA;

static unsigned long hash1(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;
}

static unsigned long hash2(const char *clave, unsigned long cap) {
  unsigned long h = 0;
  int c;
  while ((c = *clave++) != 0) {
    h = h * 131 + (unsigned long)c;
  }
  return 1 + (h % (cap - 1));
}

static int insertar_sin_rehash(HashOA *t, const char *clave, int valor) {
  unsigned long base = hash1(clave, t->capacidad);
  unsigned long paso = hash2(clave, t->capacidad);
  long primera_borrada = -1;
  for (unsigned long i = 0; i < t->capacidad; i++) {
    unsigned long idx = (base + i * paso) % t->capacidad;
    if (t->celdas[idx].estado == CELDA_OCUPADA && strcmp(t->celdas[idx].clave, clave) == 0) {
      t->celdas[idx].valor = valor;
      return 1;
    }
    if (t->celdas[idx].estado == CELDA_BORRADA && primera_borrada == -1) primera_borrada = (long)idx;
    if (t->celdas[idx].estado == CELDA_VACIA) {
      unsigned long destino = (primera_borrada != -1) ? (unsigned long)primera_borrada : idx;
      t->celdas[destino].clave = clave;
      t->celdas[destino].valor = valor;
      t->celdas[destino].estado = CELDA_OCUPADA;
      t->cantidad++;
      return 1;
    }
  }
  return 0;
}

int hash_oa_rehash(HashOA *t, unsigned long nueva_capacidad) {
  Entrada *nuevas = malloc(sizeof(Entrada) * nueva_capacidad);
  if (!nuevas) return 0;
  for (unsigned long i = 0; i < nueva_capacidad; i++) {
    nuevas[i].estado = CELDA_VACIA;
    nuevas[i].clave = NULL;
    nuevas[i].valor = 0;
  }

  Entrada *viejas = t->celdas;
  unsigned long vieja_cap = t->capacidad;
  t->celdas = nuevas;
  t->capacidad = nueva_capacidad;
  t->cantidad = 0;

  for (unsigned long i = 0; i < vieja_cap; i++) {
    if (viejas[i].estado == CELDA_OCUPADA) {
      insertar_sin_rehash(t, viejas[i].clave, viejas[i].valor);
    }
  }

  free(viejas);
  return 1;
}

static void imprimir(const HashOA *t) {
  for (unsigned long i = 0; i < t->capacidad; i++) {
    if (t->celdas[i].estado == CELDA_OCUPADA) {
      printf("[%lu] (%s -> %d)\n", i, t->celdas[i].clave, t->celdas[i].valor);
    } else if (t->celdas[i].estado == CELDA_BORRADA) {
      printf("[%lu] \n", i);
    } else {
      printf("[%lu] \n", i);
    }
  }
}

int main(void) {
  HashOA tabla = {0};
  tabla.capacidad = 7; /* primo */
  tabla.cantidad = 0;
  tabla.celdas = malloc(sizeof(Entrada) * tabla.capacidad);
  if (!tabla.celdas) return 1;
  for (unsigned long i = 0; i < tabla.capacidad; i++) tabla.celdas[i].estado = CELDA_VACIA;

  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]);
  double umbral = 0.7;

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

  printf("Tabla final:\n");
  imprimir(&tabla);

  hash_oa_rehash(&tabla, tabla.capacidad * 2 + 1);
  printf("Tras rehash manual:\n");
  imprimir(&tabla);

  free(tabla.celdas);
  return 0;
}

El rehash se dispara antes de insertar si el siguiente elemento supera el umbral de alpha. Usa doble hashing para evitar clustering.

Animacion: rehash en open addressing

Inserta juan, ana, luis, pedro, maria y sofia con doble hashing. Cuando alpha alcanza 0.7, la capacidad crece a cap * 2 + 1 y se reinsertan todas las claves.

Tabla vacia (capacidad 7). Rehash cuando alpha >= 0.70.
Cap inicial: 7 Umbral alpha: 0.70 Probing: (h1 + i*h2) % cap Pasos: h1 = djb2, h2 = 1 + (h % (cap - 1)).
Retornar