Strutture dati in C/C++

La tabella hash (hash table) in C e C++

In questa lezione conterai quante volte compare ogni parola con una tabella hash scritta a mano in C e con std::unordered_map in C++.

  • Intermedio
  • 5 min di lettura
  • 2 esempi eseguibili

Introduzione

Il problema

Per contare quante volte compare ogni parola, o per cercare un utente per nome, serve un accesso veloce per chiave. Scorrere ogni volta una lista diventa lento man mano che i dati crescono. Una tabella hash arriva quasi direttamente al posto giusto.

Immaginalo così

Una tabella hash è come una rubrica con le linguette delle lettere. È il nome stesso a dirti quale linguetta aprire, così non leggi mai tutta la rubrica. Più nomi condividono la stessa linguetta, quindi leggi solo quella pagina per trovare il nome esatto.

Dalla rubrica al codice
hash(text)🔤 Ricava la linguetta dalla chiave stessa
buckets[bucket]📑 La pagina dietro quella linguetta
item->next📝 Gli altri nomi sulla stessa pagina (chaining)
strcmp(item->key, ...)🔍 Controlla quale voce è esattamente quella che cerchi
Calcola l'hash della chiave per trovare un bucket, poi cerca solo in quel bucket.
In una frase

Una tabella hash memorizza coppie chiave-valore in un array di bucket (contenitori). Una funzione hash calcola il bucket di ogni chiave, così di solito una ricerca richiede tempo costante.

Punti importanti

  1. hash mescola i caratteri di una chiave in un numero e restituisce value % 5, un indice di bucket.
  2. Ogni Item ha un puntatore next, così le chiavi che finiscono nello stesso bucket formano una catena.
  3. Per contare una parola, il codice ne calcola l'hash, percorre la catena di quel bucket e confronta le chiavi con strcmp.
  4. In C++, std::unordered_map fa per te hash, catene e crescita: ++counts[word].

Quando usarlo

  • Contare occorrenze, come la frequenza delle parole.
  • Ricerca veloce per chiave: cache, tabelle dei simboli, record degli utenti.
  • Eliminare i duplicati o controllare se un elemento è presente.

Quando non serve

  • Ti servono le chiavi in ordine: usa std::map o ordina le chiavi.
  • Collezioni molto piccole, dove una semplice ricerca in un array è abbastanza veloce.

Guarda come funziona

Scrivi una chiave e salvala o cercala. La chiave viene trasformata dall'hash in un numero di bucket, quindi il programma va diretto al bucket giusto.

Esempi di codice C e C++

C
Esegui →
main.c
#include <stdio.h>
#include <string.h>

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}
Crea un pulsante Run per questo esempio Risultato dell'esecuzione
c=2 cpp=1
C++
Esegui →
main.cpp
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}
Crea un pulsante Run per questo esempio Risultato dell'esecuzione
c=2 cpp=1

Confronto tra C e C++

La funzione hash in C calcola un valore a partire dai caratteri della stringa e prende il resto della divisione per 5 per scegliere uno dei 5 bucket. Ogni bucket è una lista collegata, quindi le parole in collisione vengono concatenate nello stesso bucket. L'esempio in C usa poche parole fisse per concentrarsi sul meccanismo dei bucket. In C++, std::unordered_map gestisce da sola i nodi, cresce quando serve e accetta qualsiasi stringa come chiave.

C

I dati (struct) e le operazioni sono separati, e la memoria viene allocata e liberata a mano.

C++

Classi e contenitori proteggono la coerenza dei dati e gestiscono da soli le proprie risorse.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Aggiungi test per la struttura vuota e per quando raggiunge la capacità massima.
  • Scrivi la liberazione della memoria e controlla che non ci siano perdite.
  • Confronta la complessità con il contenitore equivalente della libreria standard.

Errori comuni

Confrontare chiavi stringa con ==

In C, == confronta gli indirizzi, non i caratteri.

Problema
if (item->key == word)
Correzione
if (strcmp(item->key, word) == 0)

Ignorare le collisioni

Due chiavi possono condividere un bucket, quindi devi controllare la chiave, non solo il bucket.

Problema
return buckets[hash(word)];
Correzione
for (Item *item = buckets[hash(word)]; item; item = item->next)
    if (strcmp(item->key, word) == 0) return item;

Hai finito questa lezione?

Segnala come imparata per tenere traccia dei tuoi progressi.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide