0Pricing
C Academy · Lección

Inserción, búsqueda y eliminación

Operaciones principales

Inserción, búsqueda y eliminación es una lección gratuita de C Academy en CoddyKit. Esta es la lección 3 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.

Las tres operaciones principales

Toda tabla hash admite tres operaciones: insertar, buscar y eliminar. Con una buena función hash y un factor de carga razonable, las tres se ejecutan en un tiempo medio O(1).

Construiremos paso a paso una tabla basada en encadenamiento.

Los tipos de tabla y nodo

Definimos un nodo que contiene una cadena de texto de clave copiada y un valor entero, además de una estructura de tabla que contiene el arreglo de cubetas y su capacidad.

#include <stdio.h>

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

typedef struct {
    Node **buckets;
    unsigned capacity;
    unsigned size;
} HashTable;

int main(void) {
    printf("types defined\n");
    return 0;
}

Creación de la tabla

Asigne memoria para la tabla y para un arreglo de cubetas inicializado a cero mediante calloc, de modo que cada cubeta comience con el valor NULL.

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

typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;

HashTable *ht_create(unsigned cap) {
    HashTable *t = malloc(sizeof *t);
    t->buckets = calloc(cap, sizeof(Node *));
    t->capacity = cap; t->size = 0;
    return t;
}

int main(void) {
    HashTable *t = ht_create(16);
    printf("capacity=%u size=%u\n", t->capacity, t->size);
    return 0;
}

La función auxiliar hash

Reutilizamos DJB2 y reducimos su resultado para obtener el índice de una cubeta. Esta función auxiliar se utiliza en las tres operaciones.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381; int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

unsigned bucket_of(const char *key, unsigned cap) {
    return (unsigned)(djb2(key) % cap);
}

int main(void) {
    printf("%u\n", bucket_of("name", 16));
    return 0;
}

Insertar: actualizar o anteponer

Al insertar, primero busque en la cubeta. Si la clave existe, actualice su valor. De lo contrario, asigne un nodo nuevo (con una clave copiada mediante strdup) y antepóngalo.

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

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

Node *insert(Node *head, const char *key, int val) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) { p->value = val; return head; }
    Node *n = malloc(sizeof *n);
    n->key = strdup(key); n->value = val; n->next = head;
    return n;
}

int main(void) {
    Node *b = NULL;
    b = insert(b, "a", 1);
    b = insert(b, "a", 99); /* update */
    printf("%s=%d\n", b->key, b->value);
    return 0;
}

Búsqueda

La búsqueda aplica la función hash a la clave y después recorre la lista de la cubeta comparando las claves con strcmp. Devuelve un puntero al valor (o NULL si no está presente).

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

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

int *lookup(Node *head, const char *key) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) return &p->value;
    return NULL;
}

int main(void) {
    Node n2 = {"y", 20, NULL};
    Node n1 = {"x", 10, &n2};
    int *v = lookup(&n1, "y");
    printf("%d\n", v ? *v : -1);
    return 0;
}

Eliminar: volver a enlazar la lista

La eliminación recorre la cubeta manteniendo un puntero al nodo anterior; después vuelve a enlazar la lista alrededor del elemento objetivo y libera su memoria (tanto la clave copiada como el nodo).

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

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

Node *delete_key(Node *head, const char *key) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else head = cur->next;
            free(cur->key); free(cur);
            return head;
        }
        prev = cur; cur = cur->next;
    }
    return head;
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("a"); b->value = 1; b->next = NULL;
    b = delete_key(b, "a");
    printf("%s\n", b ? "left" : "empty");
    return 0;
}

Unir todas las piezas

Una tabla completa combina estas operaciones calculando la cubeta y delegando después en las funciones auxiliares de la lista. Aquí tiene una tabla pequeña completa en funcionamiento.

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

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

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

#define CAP 16
Node *table[CAP];

void put(const char *k, int v) {
    unsigned i = djb2(k) % CAP;
    Node *n = malloc(sizeof *n);
    n->key = strdup(k); n->value = v; n->next = table[i];
    table[i] = n;
}
int get(const char *k) {
    for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
        if (!strcmp(p->key, k)) return p->value;
    return -1;
}

int main(void) {
    put("age", 30); put("score", 95);
    printf("age=%d score=%d\n", get("age"), get("score"));
    return 0;
}

Por qué copiar la clave

Almacenamos las claves con strdup para que la tabla sea propietaria de su propia copia. Si almacenáramos el puntero del código que realiza la llamada, la clave podría cambiar o liberarse mientras la utilizamos, lo que corrompería las búsquedas.

Esto también significa que la eliminación debe hacer free sobre la clave copiada.

Complejidad temporal

Con una función hash uniforme y un factor de carga cercano a 0.75:

  • Inserción: O(1) en promedio
  • Búsqueda: O(1) en promedio
  • Eliminación: O(1) en promedio

El peor caso es O(n), cuando todas las claves colisionan en una sola cubeta.

Liberación de la tabla completa

Para evitar fugas de memoria, libere todos los nodos de cada cubeta, después el arreglo de cubetas y, por último, la estructura de la tabla.

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

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

void free_bucket(Node *head) {
    while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("k"); b->value = 1; b->next = NULL;
    free_bucket(b);
    printf("freed\n");
    return 0;
}

Comprobación rápida

Compruebe su comprensión de las operaciones principales.

Resumen

Ha implementado las tres operaciones principales de una tabla hash mediante encadenamiento.

  • La inserción actualiza o antepone un nodo
  • La búsqueda recorre la lista de la cubeta con strcmp
  • La eliminación vuelve a enlazar la lista y libera tanto la clave como el nodo
  • Conserve sus propias claves mediante strdup y libere todo al destruir la tabla

Preguntas frecuentes

¿La lección «Inserción, búsqueda y eliminación» es gratis?

Sí — el texto completo de «Inserción, búsqueda y eliminación» 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 «Inserción, búsqueda y eliminación»?

Operaciones principales 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 3 de 4.

¿Cuánto tiempo toma la lección «Inserción, búsqueda y eliminación»?

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

  1. Funciones hash
  2. Gestión de colisiones
  3. Inserción, búsqueda y eliminación
  4. Redimensionamiento y factor de carga
← Volver a C Academy