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:
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
:
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.
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
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.
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
Supponiamo di partire con una hash table di dimensione \(k\), cioè una hash table in cui ci sono \(k\) liste di collisione inizialmente vuote. Supponiamo di inserire \(n\) coppie (chiave, valore), in cui tutte le chiavi sono distinte. Qual è la lunghezza media delle liste di collisione, nel caso migliore in cui l’hash delle chiavi sia uniformemente distribuito? Qual è invece la lunghezza massima di una lista di collisione nel caso peggiore?
La funzione encode()
converte una stringa di caratteri in un valore numerico, da cui si ricava l’hash tramite l’operatore modulo. Come detto sopra, la funzione encode()
non è molto sofisticata; riuscite a costruire una sequenza di chiavi diverse che producono tutte lo stesso valore hash?
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.↩