LabASD - Hash Table

Nicolas Farabegoli nicolas.farabegoli2@unibo.it

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-11

Realizziamo una tabella hash in cui le collisioni vengono gestite mediante liste (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 bisogna fare riferimento per le specifiche delle singole funzioni.

La tabella hash viene realizzata mediante una 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 (inizialmetne zero). Il campo values_count consente di conoscere in tempo \(O(1)\) il numero di coppie 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 definiti dalla struttura HashNode:

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

Nella Figura 1 viene mostrato un esempio di tabella hash.

Figura 1: Esempio di tabella hash; Nota: non necessariamente le chiavi generano delle collisioni come mostrato
Figura 1: Esempio di tabella hash; Nota: non necessariamente le chiavi generano delle collisioni come mostrato

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 numero ottenuto sommando i codici ASCII di tutti i caratteri della stringa1. hash_function(h,k) accetta come parametri una tabella hash h e un intero k, e restituisce un intero appartenente all'intervallo \(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.

Il programma hashtable-main.c contiene una funzione main() che legge da standard input una sequenza di comandi, uno per ogni riga, che manipolano una tabella hash inizialmente vuota.

Il file di comandi, di cui viene fornito un esempio nel file hashtable.in contiene una sequenza di comandi, descritti nella tabella seguente:

Comando Significato
n Inizializza l'array dei puntatori a liste di collisione alla dimensione n ; questa istruzione compare una sola volta all'inizio
+ 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

Le chiavi key sono stringhe che non contengono spazi, in modo da facilitarne la lettura. I valori val sono interi.

Nel caso in cui si tenti di inserire un elemento la cui chiave è gia 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 implementazione rispecchia il modo in cui vengono gestite le strutture hash in altri linguaggi di programmazione (es., Java).

Per compilare:

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

PEr eseguire:

    ./hashtable-main < hashtable.in

oppure

    ./hashtable-main hashtable.in

Per approfondire

File


  1. Sommare banalmente i codici ASCII è una pessima idea perché può produrre collisioni in modo troppo predicibile. Tale funzione quindi non va usata in applicazioni reali. Una funzione alternativa che viene spesso raccomandata è djb2 descritta qui.