0Pricing
C Academy · Lezione

Inserimento, ricerca e cancellazione

Operazioni fondamentali

Inserimento, ricerca e cancellazione è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Le tre operazioni fondamentali

Ogni tabella hash supporta tre operazioni: insert, lookup e delete. Con una buona funzione hash e un fattore di carico ragionevole, tutte e tre hanno un tempo medio O(1).

Costruiremo passo dopo passo una tabella basata sul concatenamento.

I tipi di tabella e nodo

Definiamo un nodo che contiene una stringa di chiave copiata e un valore intero, oltre a una struct della tabella che contiene l'array dei bucket e la relativa capacità.

#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;
}

Creazione della tabella

Allochiamo la tabella e un array di bucket inizializzato a zero con calloc, così ogni bucket inizialmente contiene 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 funzione hash di supporto

Riutilizziamo DJB2 e lo riduciamo a un indice del bucket. Questa funzione di supporto viene usata da tutte e tre le operazioni.

#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;
}

Inserimento: aggiornamento o inserimento in testa

Durante l'inserimento, cerchiamo prima nel bucket. Se la chiave esiste, ne aggiorniamo il valore. Altrimenti allochiamo un nuovo nodo (con una chiave copiata tramite strdup) e lo inseriamo in testa.

#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;
}

Ricerca

La ricerca calcola l'hash della chiave, quindi percorre la lista del bucket confrontando le chiavi con strcmp. Restituisce un puntatore al valore (oppure NULL se la chiave non è 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;
}

Eliminazione: ricollegare la lista

L'eliminazione percorre il bucket mantenendo un puntatore al nodo precedente, quindi ricollega la lista intorno all'elemento cercato e lo libera (sia la chiave copiata sia il 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;
}

Assemblaggio della tabella

Una tabella completa riunisce queste operazioni calcolando il bucket e delegando quindi alle funzioni di supporto delle liste. Ecco una piccola tabella completa in azione.

#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;
}

Perché copiare la chiave

Memorizziamo le chiavi con strdup, così la tabella possiede una copia propria. Se memorizzassimo il puntatore fornito dal chiamante, la chiave potrebbe cambiare o essere liberata mentre la utilizziamo, corrompendo le ricerche.

Questo significa anche che l'eliminazione deve eseguire free sulla chiave copiata.

Complessità temporale

Con una funzione hash uniforme e un fattore di carico mantenuto vicino a 0.75:

  • Inserimento: O(1) in media
  • Ricerca: O(1) in media
  • Eliminazione: O(1) in media

Il caso peggiore è O(n), quando tutte le chiavi entrano in collisione nello stesso bucket.

Liberazione dell'intera tabella

Per evitare perdite di memoria, liberiamo ogni nodo di ogni bucket, poi l'array dei bucket e infine la struct della tabella.

#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;
}

Verifica rapida

Verifichi la Sua comprensione delle operazioni fondamentali.

Riepilogo

Ha implementato le tre operazioni fondamentali delle tabelle hash con concatenamento.

  • L'inserimento aggiorna un nodo o lo inserisce in testa
  • La ricerca percorre la lista del bucket con strcmp
  • L'eliminazione ricollega la lista e libera sia la chiave sia il nodo
  • La tabella possiede le proprie chiavi tramite strdup e libera tutto durante la distruzione

Domande Frequenti

La lezione «Inserimento, ricerca e cancellazione» è gratuita?

Sì — il testo completo di «Inserimento, ricerca e cancellazione» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Inserimento, ricerca e cancellazione»?

Operazioni fondamentali Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «Inserimento, ricerca e cancellazione»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Funzioni hash
  2. Gestione delle collisioni
  3. Inserimento, ricerca e cancellazione
  4. Ridimensionamento e fattore di carico
← Torna a C Academy