C Academy · Lección

Gestión de colisiones

Encadenamiento y sondeo

Gestión de colisiones es una lección gratuita de C Academy en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.

El problema de las colisiones

Se produce una colisión cuando dos claves distintas generan el mismo hash y apuntan a la misma cubeta. Como las colisiones son inevitables, toda tabla hash necesita una estrategia para almacenar varias claves en una misma posición.

Las dos familias principales son el encadenamiento y el direccionamiento abierto.

Encadenamiento separado

Con el encadenamiento separado, cada cubeta contiene una lista enlazada de entradas. Cuando ocurre una colisión, simplemente añade (o antepone) la entrada a la lista de esa cubeta.

Las cubetas almacenan punteros al primer elemento de las listas
Las búsquedas recorren una lista corta

Estructura de los nodos del encadenamiento

Cada nodo almacena una clave, un valor y un puntero next. La tabla es un arreglo de punteros a nodos.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

Inserción con encadenamiento

Añadir al principio de la lista de la cubeta tiene un coste O(1). Aquí construimos manualmente una cadena pequeña y la imprimimos.

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

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

Direccionamiento abierto

Con el direccionamiento abierto, cada entrada vive directamente en el arreglo de cubetas. Cuando ocurre una colisión, se realiza un sondeo para encontrar otra posición vacía usando una secuencia fija.

No se asignan nodos adicionales, lo que favorece el uso de la caché.

Sondeo lineal

El sondeo lineal comprueba la siguiente posición, luego la siguiente, y vuelve al principio al llegar al final: (h + i) % capacity.

Es sencillo y favorece el uso de la caché, pero sufre de agrupamiento.

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

Sondeo cuadrático

El sondeo cuadrático utiliza (h + i*i) % capacity para distribuir los sondeos y reducir el agrupamiento primario.

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

Doble dispersión

La doble dispersión utiliza una segunda función hash para determinar el tamaño del paso: (h1 + i*h2) % capacity. Esto proporciona a cada clave su propia secuencia de sondeo y la mejor distribución de las tres técnicas.

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

Eliminación en el direccionamiento abierto

No puede simplemente borrar una posición en el direccionamiento abierto, porque rompería las cadenas de sondeo de otras claves. En su lugar, márquela con un marcador de borrado para que las búsquedas sigan sondeando después de ella.

Encadenamiento frente a direccionamiento abierto

Compensaciones:

Encadenamiento: admite factores de carga altos y facilita las eliminaciones, pero utiliza punteros y asignaciones de memoria
Direccionamiento abierto: favorece la caché y no requiere asignaciones por entrada, pero se degrada considerablemente cuando la tabla está casi llena y necesita marcadores de borrado

Demostración del número de sondeos

El sondeo lineal puede necesitar varios pasos cuando las posiciones se agrupan. Aquí contamos los sondeos necesarios para encontrar una posición libre.

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

Comprobación rápida

Compruebe sus conocimientos sobre el tratamiento de colisiones.

Resumen

Ha explorado cómo resuelven las colisiones las tablas hash.

El encadenamiento almacena una lista enlazada por cubeta
El direccionamiento abierto sondea hasta encontrar una posición libre
Variantes del sondeo: lineal, cuadrático y doble dispersión
El direccionamiento abierto necesita marcadores de borrado para eliminar elementos

Preguntas frecuentes

¿La lección «Gestión de colisiones» es gratis?

Sí — el texto completo de «Gestión de colisiones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Gestión de colisiones»?

Encadenamiento y sondeo Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar C Academy?

No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.

¿Cuánto tiempo toma la lección «Gestión de colisiones»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de C Academy?

Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

← Volver a C Academy