Hash Table in C

Le hash table sono una struttura dati estremamente efficiente per la ricerca, l’inserimento e la cancellazione di dati. Utilizzano una funzione hash per calcolare l’indice di un array dove i dati possono essere memorizzati o recuperati rapidamente. In questa guida, esploreremo come implementare una hash table in C, comprese le tecniche per risolvere le collisioni e ottimizzare le prestazioni.

Cos’è una Hash Table?

Una hash table è una struttura dati che associa chiavi a valori. Utilizza una funzione hash per convertire una chiave in un indice di un array. Questo rende l’accesso ai dati molto rapido, tipicamente O(1) nel caso medio.

Funzione Hash

Una funzione hash prende una chiave e la trasforma in un indice dell’array della hash table. La qualità della funzione hash influisce direttamente sulle prestazioni della hash table.

Esempio di Funzione Hash Semplice

unsigned int hash(const char* chiave) {
    unsigned int valore_hash = 0;
    while (*chiave) {
        valore_hash = (valore_hash << 5) + *chiave++;
    }
    return valore_hash;
}

Implementazione di una Hash Table

Definizione della Struttura di una Hash Table

Per implementare una hash table, utilizzeremo una struttura che contiene un array di bucket. Ogni bucket può contenere un puntatore a una lista collegata per gestire le collisioni.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 100

struct Nodo {
    char* chiave;
    char* valore;
    struct Nodo* prossimo;
};

struct HashTable {
    struct Nodo* bucket[SIZE];
};

Creazione della Hash Table

struct HashTable* crea_hash_table() {
    struct HashTable* tabella = (struct HashTable*)malloc(sizeof(struct HashTable));
    for (int i = 0; i < SIZE; i++) {
        tabella->bucket[i] = NULL;
    }
    return tabella;
}

Inserimento di un Elemento nella Hash Table

Per inserire un elemento, calcoliamo l’indice usando la funzione hash e inseriamo il dato nel bucket appropriato.

void inserisci(struct HashTable* tabella, const char* chiave, const char* valore) {
    unsigned int indice = hash(chiave) % SIZE;
    struct Nodo* nuovo_nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nuovo_nodo->chiave = strdup(chiave);
    nuovo_nodo->valore = strdup(valore);
    nuovo_nodo->prossimo = tabella->bucket[indice];
    tabella->bucket[indice] = nuovo_nodo;
}

Ricerca di un Elemento nella Hash Table

Per cercare un elemento, calcoliamo l’indice e attraversiamo la lista collegata in quel bucket fino a trovare la chiave corrispondente.

char* cerca(struct HashTable* tabella, const char* chiave) {
    unsigned int indice = hash(chiave) % SIZE;
    struct Nodo* nodo = tabella->bucket[indice];
    while (nodo) {
        if (strcmp(nodo->chiave, chiave) == 0) {
            return nodo->valore;
        }
        nodo = nodo->prossimo;
    }
    return NULL;  // Chiave non trovata
}

Cancellazione di un Elemento nella Hash Table

La cancellazione richiede di trovare il nodo nella lista collegata, rimuoverlo e liberare la memoria.

void cancella(struct HashTable* tabella, const char* chiave) {
    unsigned int indice = hash(chiave) % SIZE;
    struct Nodo* nodo = tabella->bucket[indice];
    struct Nodo* precedente = NULL;

    while (nodo && strcmp(nodo->chiave, chiave) != 0) {
        precedente = nodo;
        nodo = nodo->prossimo;
    }

    if (nodo == NULL) {
        printf("Chiave non trovata\n");
        return;
    }

    if (precedente == NULL) {
        tabella->bucket[indice] = nodo->prossimo;
    } else {
        precedente->prossimo = nodo->prossimo;
    }

    free(nodo->chiave);
    free(nodo->valore);
    free(nodo);
}

Esempio Completo di Utilizzo

int main() {
    struct HashTable* tabella = crea_hash_table();

    inserisci(tabella, "nome", "Alice");
    inserisci(tabella, "città", "Roma");
    inserisci(tabella, "paese", "Italia");

    printf("Nome: %s\n", cerca(tabella, "nome"));
    printf("Città: %s\n", cerca(tabella, "città"));

    cancella(tabella, "città");

    if (cerca(tabella, "città") == NULL) {
        printf("Città non trovata\n");
    }

    return 0;
}

Uscita:

Nome: Alice
Città: Roma
Città non trovata

Gestione delle Collisioni

Le collisioni si verificano quando due chiavi diverse producono lo stesso indice. Per gestire le collisioni, la soluzione più comune è l’encasellamento concatenato (chaining), che memorizza tutti gli elementi con lo stesso indice in una lista collegata.

Vantaggi dell’Encasellamento Concatenato

• Flessibilità: Le collisioni sono gestite in modo semplice e lineare.
• Scalabilità: Il numero di elementi in ogni bucket può crescere senza limiti (compatibilmente con la memoria).

Considerazioni sull’Uso delle Hash Table

• Funzione Hash Efficiente: Una buona funzione hash distribuisce le chiavi uniformemente tra i bucket, riducendo le collisioni e migliorando le prestazioni.
• Dimensione della Hash Table: La dimensione della hash table (numero di bucket) dovrebbe essere scelta in base al numero di elementi attesi per minimizzare le collisioni.
• Gestione della Memoria: È essenziale gestire correttamente l’allocazione e la deallocazione della memoria per evitare perdite di memoria (memory leaks).

Conclusioni

Le hash table in C offrono un metodo estremamente efficiente per la gestione di dati associati a chiavi, consentendo operazioni di ricerca, inserimento e cancellazione in tempo costante nel caso medio. Con una funzione hash ben progettata e una gestione appropriata delle collisioni, le hash table possono migliorare significativamente le prestazioni di un programma, rendendole una scelta ideale per molte applicazioni che richiedono l’accesso rapido ai dati.