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++.
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.
hash(text)🔤 Ricava la linguetta dalla chiave stessabuckets[bucket]📑 La pagina dietro quella linguettaitem->next📝 Gli altri nomi sulla stessa pagina (chaining)strcmp(item->key, ...)🔍 Controlla quale voce è esattamente quella che cerchiUna 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
hashmescola i caratteri di una chiave in un numero e restituiscevalue % 5, un indice di bucket.- Ogni
Itemha un puntatorenext, così le chiavi che finiscono nello stesso bucket formano una catena. - Per contare una parola, il codice ne calcola l'hash, percorre la catena di quel bucket e confronta le chiavi con
strcmp. - In C++,
std::unordered_mapfa 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::mapo 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++
#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);
}
c=2 cpp=1
#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';
}
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.
I dati (struct) e le operazioni sono separati, e la memoria viene allocata e liberata a mano.
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.
if (item->key == word)
if (strcmp(item->key, word) == 0)
Ignorare le collisioni
Due chiavi possono condividere un bucket, quindi devi controllare la chiave, non solo il bucket.
return buckets[hash(word)];
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.
- Primo Carattere Unico Trova il primo carattere che compare una sola volta. Facile
- Frequenza dei caratteri Conta quante volte appare ciascun carattere. Facile