ADT Tabella di Simboli

ADT Tabella di Simboli

L’ADT (Abstract Data Type) Tabella di simboli o hashtable è un tipo di dato astratto utilizzato per codificare i dati per renderli facilmente ricercabili come vantaggio principale.
L’ADT contiene tra le sue funzioni di gestione, una funzione che si occupa di codificare il dato in ingresso in un numero intero, tale funzione viene chiamata funzione di hash, di cui ne esistono diverse varianti più o meno ottimizzate.
L’intero ritornato dalla funzione di hash permette di memorizzare il dato in ingresso all’interno di un vettore allocato dinamicamente nella cella con indice l’intero trovato dopo l’operazione di hashing; ciò permette di avere complessità O(1) nella ricerca della cella col dato ricercato. Più difficile risulta la cancellazione di un dato dalla tabella di simboli, in quanto è necessario gestire la cancellazione in modo fittizio o in modo reale e permettere all’algoritmo di ricerca di non essere tratto in inganno da precedenti operazioni di cancellazione che potrebbero comprometterne l’utilizzo. La gestione della cancellazione è necessaria soprattutto a causa delle metodologie utilizzate nel caso delle operazioni di hashing che riportano indici già utilizzati e quindi vi è il rischio di perdere la traccia dell’elemento ricercato.
Un semplice wrapper dell’ADT tabella di simboli è:

struct hashtable{
int M; //maxN
int N; //celle riempite
struct dati *vett;
}

struct dati rappresenta una struttura contenente i dati passati dalla funzione di hash.