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++.

Introduzione

Una tabella hash (hash table) usa una funzione hash (hash function) per trasformare ogni chiave nell'indice di un contenitore (bucket), rendendo ricerca, inserimento ed eliminazione molto veloci. Quando due chiavi diverse finiscono nello stesso bucket si ha una collisione (collision), e la tabella ha bisogno di una strategia come il concatenamento (chaining) o l'indirizzamento aperto (open addressing).

Punti importanti

Definisci le condizioni che devono essere sempre vere (invarianti) prima di scrivere le operazioni.
Gestisci i casi di struttura vuota, piena e di allocazione di memoria fallita.
Valuta insieme la complessità e la gestione della memoria di ogni operazione.

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++

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

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

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.

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.

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