5 - Encadenamiento (Separate Chaining)
Concepto general
El encadenamiento resuelve colisiones almacenando, en cada bucket del array, una estructura enlazada (usualmente una lista). Cuando varias claves apuntan al mismo indice, se agregan como nodos dentro de la lista de ese bucket.
5.1 Concepto basico
Cada bucket apunta al inicio de una lista de pares clave-valor. Insertar implica agregar un nodo en esa lista; buscar y eliminar consisten en recorrerla hasta hallar la clave.
5.2 Lista enlazada en cada bucket
Una lista simple por bucket mantiene el orden de insercion y simplifica altas y bajas sin reubicar otros elementos.
5.3 Representacion del bucket en C
#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;
HashTable *hash_crear(unsigned long capacidad) {
HashTable *t = malloc(sizeof(HashTable));
t->capacidad = capacidad;
t->cantidad = 0;
t->buckets = calloc(capacidad, sizeof(HashNode *));
return t;
}Cada entrada del array buckets almacena el puntero al primer nodo de la lista correspondiente. El campo cantidad facilita calcular el factor de carga.
5.4 Insercion con encadenamiento
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;
}
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; /* actualiza */
return 1;
}
nodo = nodo->sig;
}
HashNode *nuevo = malloc(sizeof(HashNode));
nuevo->clave = clave;
nuevo->valor = valor;
nuevo->sig = t->buckets[idx]; /* insercion al frente */
t->buckets[idx] = nuevo;
t->cantidad++;
return 1;
}Se recorre la lista del bucket buscando la clave; si ya existe se actualiza el valor, de lo contrario se agrega un nodo al inicio.
5.5 Busqueda
HashNode *hash_buscar(HashTable *t, const char *clave) {
unsigned long idx = hash_cadena(clave, t->capacidad);
HashNode *nodo = t->buckets[idx];
while (nodo != NULL) {
if (strcmp(nodo->clave, clave) == 0) return nodo;
nodo = nodo->sig;
}
return NULL;
}La busqueda queda acotada a la longitud de la lista dentro del bucket, en lugar de revisar toda la tabla.
5.6 Eliminacion
int hash_eliminar(HashTable *t, const char *clave) {
unsigned long idx = hash_cadena(clave, t->capacidad);
HashNode *actual = t->buckets[idx];
HashNode *anterior = NULL;
while (actual != NULL) {
if (strcmp(actual->clave, clave) == 0) {
if (anterior == NULL) {
t->buckets[idx] = actual->sig;
} else {
anterior->sig = actual->sig;
}
free(actual);
t->cantidad--;
return 1;
}
anterior = actual;
actual = actual->sig;
}
return 0; /* clave no encontrada */
}Eliminar requiere llevar un puntero previo para ajustar el enlace cuando se quita el nodo objetivo.
5.7 Complejidad temporal
- Insercion: O(1) promedio; O(k) si la lista del bucket tiene k nodos.
- Busqueda: O(1) promedio; O(k) en el peor caso dentro del bucket.
- Eliminacion: O(1) promedio; O(k) con el mismo razonamiento.
La clave para sostener O(1) promedio es mantener el factor de carga bajo y una funcion hash que disperse bien.
5.8 Ventajas y desventajas
- Ventajas: borrados simples, implementacion directa con listas, tolera factores de carga mas altos que el open addressing.
- Desventajas: usa memoria extra por nodos, peor localidad de cache, el peor caso puede crecer si las listas se alargan.
5.9 Problemas mas comunes
- Listas largas: indican falta de rehashing o funcion hash pobre; revisar factor de carga.
- Fugas de memoria: olvidar liberar nodos al rehash o al destruir la tabla.
- Claves duplicadas: no actualizar el valor existente puede generar multiples nodos con la misma clave.
- Uso de cadenas temporales: guardar punteros a buffers que luego se liberan provoca lecturas invalidas; duplicar cadenas si es necesario.
5.10 Ejercicio completo para probar en CLion
Copia el siguiente programa en main.c, compila y ejecuta. Inserta, busca y elimina claves usando encadenamiento, y muestra el estado final de la tabla.
La clave de la tabla de hash es el nombre y su valor asociado es la edad de dicha persona.
#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));
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));
nuevo->clave = clave;
nuevo->valor = valor;
nuevo->sig = t->buckets[idx];
t->buckets[idx] = nuevo;
t->cantidad++;
return 1;
}
HashNode *hash_buscar(HashTable *t, const char *clave) {
unsigned long idx = hash_cadena(clave, t->capacidad);
HashNode *nodo = t->buckets[idx];
while (nodo != NULL) {
if (strcmp(nodo->clave, clave) == 0) return nodo;
nodo = nodo->sig;
}
return NULL;
}
int hash_eliminar(HashTable *t, const char *clave) {
unsigned long idx = hash_cadena(clave, t->capacidad);
HashNode *actual = t->buckets[idx];
HashNode *anterior = NULL;
while (actual != NULL) {
if (strcmp(actual->clave, clave) == 0) {
if (anterior == NULL) {
t->buckets[idx] = actual->sig;
} else {
anterior->sig = actual->sig;
}
free(actual);
t->cantidad--;
return 1;
}
anterior = actual;
actual = actual->sig;
}
return 0;
}
void hash_imprimir(HashTable *t) {
for (unsigned long i = 0; i < t->capacidad; i++) {
printf("[%lu]: ", i);
HashNode *n = t->buckets[i];
while (n != NULL) {
printf("(%s -> %d) ", n->clave, n->valor);
n = n->sig;
}
printf("\n");
}
}
void hash_destruir(HashTable *t) {
for (unsigned long i = 0; i < t->capacidad; i++) {
HashNode *n = t->buckets[i];
while (n != NULL) {
HashNode *tmp = n->sig;
free(n);
n = tmp;
}
}
free(t->buckets);
free(t);
}
int main(void) {
HashTable *tabla = hash_crear(8);
hash_insertar(tabla, "juan", 50);
hash_insertar(tabla, "ana", 23);
hash_insertar(tabla, "luis", 19);
hash_insertar(tabla, "pedro", 90);
hash_insertar(tabla, "maria", 41);
printf("Tabla final:\n");
hash_imprimir(tabla);
HashNode *resultado = hash_buscar(tabla, "pedro");
printf("Buscar 'pedro': %s\n", resultado ? "encontrado" : "no encontrado");
hash_eliminar(tabla, "pedro");
resultado = hash_buscar(tabla, "pedro");
printf("Buscar 'pedro': %s\n", resultado ? "encontrado" : "no encontrado");
hash_destruir(tabla);
return 0;
}En CLion, crea un proyecto de consola, reemplaza main.c con el codigo anterior y ejecuta. Observa como las colisiones se guardan en listas dentro de cada bucket.
Animacion de insercion en la tabla
Pulsa el boton para ver como se insertan juan, ana, luis, pedro y maria usando el hash djb2 sobre 8 buckets. Cada colision se encadena al frente, igual que en el codigo en C.
