LabASD - Tabelle Hash

Nicolas Farabegoli

Moreno Marzolla

Ultimo aggiornamento: 2024-03-18

Realizzare una tabella hash in cui le collisioni vengono gestite mediante liste di collisione (chaining). Le chiavi sono stringhe di caratteri zero-terminate, come le normali stringhe in C; ad ogni chiave è associato un valore intero, da trattare come “dato satellite”. L’interfaccia della struttura dati è descritta nel file hashtable.h a cui si rimanda per le specifiche delle singole funzioni.

La tabella hash è rappresentata dalla struttura HashTable così definita:

typedef struct {
    HashNode **items;
    int size;
    int values_count;
} HashTable;

dove items è un array di size puntatori, ciascuno dei quali punta all’inizio della lista di collisione, e values_count è il numero di coppie (chiave, valore) presenti nella tabella hash (inizialmente zero). Il campo values_count consente di conoscere in tempo \(O(1)\) il numero di chiavi presenti nella hashtable, senza doverle contare di volta in volta. Tale informazione può essere mantenuta aggiornata in tempo \(O(1)\) durante l’esecuzione delle altre operazioni.

I nodi delle liste di collisione sono rappresentati dalla struttura HashNode:

typedef struct HashNode {
    char *key;
    int value;
    struct HashNode *next;
} HashNode;

Come si vede, si tratta di una normale implementazione di liste concatenate, in cui ogni nodo ha un puntatore al nodo successivo; l’ultimo nodo della lista ha NULL come successore. In questa implementazione non è richiesto di mantenere ordinato il contenuto delle liste di collisione; è quindi possibile aggiungere i nuovi nodi dalla testa, in modo da semplificare il codice.

Nella Figura 1 viene mostrato un esempio.

Figura 1: Esempio di tabella hash con size = 10
Figura 1: Esempio di tabella hash con size = 10

Vengono fornite due funzioni encode(key) e hash_function(h,k) per associare le chiavi (stringhe) agli slot della tabella hash. La funzione encode(key) trasforma una stringa in un valore intero ottenuto sommando i codici ASCII di tutti i caratteri1.

Non è possibile usare direttamente il risultato per indicizzare la tebella hash, dato che encode() potrebbe restituire un valore superiore alla dimensione della tabella hash. Occorre invece usare la funzione

unsigned long hash_function(const HashTable *table, unsigned long k)

che accetta come parametri un puntatore ad una tabella hash h e un intero k di tipo unsigned long, e restituisce un intero appartenente all’insieme \(\{0, \ldots, \texttt{h->size}-1\}\) usando l’operatore modulo. Il valore prodotto da hash_function() viene usato come indice dell’array h->items[] per decidere in quale lista di trabocco inserire la chiave data.

L’uso di due funzioni separate, encode() e hash_function(), per associare una stringa ad un elemento dell’array, è motivato dal fatto che nel libro di testo si da per scontato che le chiavi siano interi, mentre nel nostro caso le chiavi sono stringhe. Ho quindi deciso di rendere esplicita la fase di trasformazione di una stringa in un intero, che poi viene usato nella funzione hash.

Il programma hashtable-main.c legge una sequenza di comandi da un file il cui nome va passato sulla riga di comando. I comandi manipolano una tabella hash inizialmente vuota, e sono descritti nella Tabella 1. Il file hashtable.in contiene un esempio di input.

Tabella 1: Comandi nel file di input
Comando Significato
n Inizializza la tabella hash creando n puntatori a liste di collisione, inizialmente vuote; questa istruzione deve comparire una sola volta all’inizio del file.
+ key val Inserisce la chiave key con valore val.
- key Cancella la chiave key e il valore associato, se presenti.
? key Restituisce il valore associato alla chiave key, se presente, oppure un opportuno messaggio che indica che la chiave non è presente.
c Svuota la tabella hash.
s Restituisce il numero di coppie (chiave, valore) presenti nella tabella hash.
p Stampa il contenuto della tabella hash in forma leggibile; usare per debug.

Le chiavi key sono stringhe che non contengono spazi; i valori val sono interi.

Nel caso in cui si tenti di inserire una chiave già presente nella tabella, occorre aggiornare il vecchio valore con quello nuovo (si faccia riferimento alla specifica della funzione hash_insert() nel file hashtable.h). Tale comportamento rispecchia il modo in cui vengono gestite le tabelle hash in altri linguaggi di programmazione, come ad esempio Java.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic hashtable.c hashtable-main.c -o hashtable-main

Per eseguire in ambiente Linux/MacOSX:

    ./hashtable-main hashtable.in

Per eseguire in ambiente Windows:

    .\hashtable-main hashtable.in

Per approfondire

File


  1. Sommare i codici ASCII non è una buona idea, sia perché se non viene fatto attentamente può causare overflow, sia perché può produrre collisioni in modo troppo prevedibile. La funzione encode() non andrebbe quindi usata in applicazioni reali. Una funzione hash che viene talvolta raccomandata è djb2.