Concetti Chiave
- La gestione delle collisioni nelle hashtable è fondamentale per garantire l'efficienza delle operazioni e il corretto funzionamento della struttura dati.
- Tra i metodi di gestione delle collisioni, il linear chaining utilizza un vettore di puntatori per collegare i dati che condividono lo stesso indice hash, formando liste di collisione.
- Il linear probing, metodo di open addressing, risolve le collisioni incrementando l'indice fino a trovare una cella disponibile, confrontando i dati durante la ricerca.
- Il double hashing impiega due funzioni di hash per gestire le collisioni, utilizzando la seconda funzione quando la prima genera una collisione, fino a trovare uno spazio libero.
- Ogni metodo presenta vantaggi e svantaggi specifici, influenzando le prestazioni della tabella di simboli in base al tipo di dati e alle operazioni eseguite.
La gestione delle collisioni in una tabella di simboli (hashtable) è un’operazione molto delicata in quanto determina la complessità delle sue operazioni ed il suo completo funzionamento.
Quali sono i metodi di gestione delle collisioni?
Esistono diversi metodi dedicati alla gestione delle collisioni (valori uguali ritornati dalla funzione di hash per dati diversi), linear chaining, open addressing con linear probing e open addressing con double hashing come più importanti metodi presenti in letteratura.
- Linear Chaining: con il linear chaining il vettore allocato dinamicamente nell’ADT è un vettore di puntatori, difatti in caso di collisioni si aggancia alla cella dell’indice trovato il nuovo dato, andando a creare per ogni cella una lista dei dati che hanno quell’indice come valore di ritorno della funzione di hash, durante la ricerca, dopo aver trovato l’indice, si scorre la relativa lista e si confrontano i dati per trovare quello cercato;
- Open addressing con linear probing: con il linear probing in caso si riscontrino delle collisioni dalla funzione di hash, l’intero trovato viene incrementato di un’unità finché non viene raggiunta una cella disponibile per il dato; stessa cosa viene fatta durante la ricerca e per ogni passo viene confrontato il dato con quello della cella per verificarne l’uguaglianza;
- Open addressing con double hashing: con il double hashing vengono definite due funzioni di hash, se la prima dà una collisione allora si sfruttano entrambe passando alla seconda il risultato del passo precedente, fino a trovare uno spazio disponibile.
Open addressing con linear probing
Open addressing con double hashing
Domande da interrogazione
- Quali sono i principali metodi di gestione delle collisioni in una tabella di simboli?
- Come funziona il linear chaining nella gestione delle collisioni?
- Qual è la differenza tra open addressing con linear probing e open addressing con double hashing?
I principali metodi di gestione delle collisioni includono il linear chaining, l'open addressing con linear probing e l'open addressing con double hashing, come evidenziato nel testo.
Nel linear chaining, si utilizza un vettore di puntatori che, in caso di collisioni, crea una lista di dati per ogni cella dell'indice trovato, permettendo di scorrere e confrontare i dati durante la ricerca.
Nel linear probing, si incrementa l'indice fino a trovare una cella disponibile, mentre nel double hashing si utilizzano due funzioni di hash per risolvere le collisioni, passando alla seconda funzione se la prima genera una collisione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
