Hashtable gestione delle collisioni

Hashtable gestione delle collisioni

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.
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.