Concetti Chiave
- L'ADT Tabella di simboli, o hashtable, consente una ricerca rapida grazie all'uso di una funzione di hash che codifica i dati in numeri interi.
- La funzione di hash permette di memorizzare i dati in un vettore dinamico, garantendo una complessità di ricerca di O(1).
- La gestione della cancellazione è complessa e richiede strategie per evitare confusioni durante le operazioni di ricerca, a causa di precedenti cancellazioni.
- La struttura della hashtable include variabili per gestire il numero massimo di celle e celle attualmente riempite, insieme a un vettore per i dati.
- Le varianti della funzione di hash possono essere ottimizzate per migliorare ulteriormente l'efficienza della 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.
Che cos'è la funzione di hash e come si applica alla memorizzazione?
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.
Gestione della cancellazione
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.
Struttura della hashtable
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.
Domande da interrogazione
- Qual è il principale vantaggio dell'ADT Tabella di simboli?
- Come viene gestita la cancellazione dei dati in una hashtable?
- Qual è la struttura di base di una hashtable?
Il principale vantaggio dell'ADT Tabella di simboli, o hashtable, è la sua capacità di rendere i dati facilmente ricercabili, grazie alla funzione di hash che consente una complessità O(1) nella ricerca (come indicato nel testo).
La cancellazione dei dati in una hashtable è complessa e può avvenire in modo fittizio o reale, per evitare che l'algoritmo di ricerca venga ingannato da operazioni di cancellazione precedenti, come descritto nel testo.
La struttura di base di una hashtable include un massimo di celle (M), il numero di celle riempite (N) e un vettore di dati allocato dinamicamente, come illustrato nella definizione della struct hashtable nel testo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
