C Academy · Lezione

Gestione delle collisioni

Chaining e probing

Gestione delle collisioni è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 2 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.

Il problema delle collisioni

Si verifica una collisione quando due chiavi distinte producono lo stesso bucket. Poiché le collisioni sono inevitabili, ogni tabella hash ha bisogno di una strategia per memorizzare più chiavi in una stessa posizione.

Le due famiglie principali sono il concatenamento e l'indirizzamento aperto.

Concatenamento separato

Con il concatenamento separato, ogni bucket contiene una lista concatenata di elementi. In caso di collisione, è sufficiente aggiungere l'elemento in coda (o in testa) alla lista del bucket.

I bucket memorizzano i puntatori alle teste delle liste
Le ricerche percorrono una lista breve

Struttura dei nodi del concatenamento

Ogni nodo memorizza una chiave, un valore e un puntatore next. La tabella è un array di puntatori ai nodi.

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

Inserimento con concatenamento

L'inserimento in testa alla lista del bucket ha costo O(1). Qui costruiamo manualmente una piccola catena e la stampiamo.

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

Indirizzamento aperto

Con l'indirizzamento aperto, ogni elemento risiede direttamente nell'array dei bucket. In caso di collisione, si esegue il probe di un altro slot vuoto usando una sequenza fissa.

Non vengono allocati nodi aggiuntivi, caratteristica favorevole alla cache.

Scansione lineare

La scansione lineare controlla lo slot successivo, poi quello dopo ancora, ricominciando dall'inizio quando raggiunge la fine: (h + i) % capacity.

È semplice e favorevole alla cache, ma soffre del clustering.

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

Scansione quadratica

La scansione quadratica usa (h + i*i) % capacity per distribuire i probe e ridurre il clustering 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;
}

Doppio hashing

Il doppio hashing usa un secondo hash per determinare il passo: (h1 + i*h2) % capacity. In questo modo ogni chiave ha una propria sequenza di probe e si ottiene la distribuzione migliore delle tre.

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

Eliminazione con indirizzamento aperto

Con l'indirizzamento aperto non è possibile svuotare semplicemente uno slot, perché si interromperebbero le catene di probe di altre chiavi. È invece necessario contrassegnarlo con un tombstone, così le ricerche continuano oltre quello slot.

Concatenamento e indirizzamento aperto

Compromessi:

Concatenamento: gestisce fattori di carico elevati e consente eliminazioni semplici, ma usa puntatori e allocazioni
Indirizzamento aperto: è favorevole alla cache e non richiede allocazioni per elemento, ma peggiora drasticamente quando la tabella è quasi piena e richiede tombstone

Dimostrazione del numero di probe

La scansione lineare può richiedere diversi passaggi quando gli slot formano dei raggruppamenti. Qui contiamo i probe necessari per trovare uno slot libero.

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

Verifica rapida

Verifichi le Sue conoscenze sulla gestione delle collisioni.

Riepilogo

Ha esplorato il modo in cui le tabelle hash risolvono le collisioni.

Il concatenamento memorizza una lista concatenata per ogni bucket
L'indirizzamento aperto esegue probe per trovare uno slot libero
Varianti del probing: lineare, quadratico e doppio hashing
L'indirizzamento aperto richiede tombstone per le eliminazioni

Domande Frequenti

La lezione «Gestione delle collisioni» è gratuita?

Sì — il testo completo di «Gestione delle collisioni» è 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 «Gestione delle collisioni»?

Chaining e probing 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 2 di 4.

Quanto tempo richiede la lezione «Gestione delle collisioni»?

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

← Torna a C Academy