CONCATENAZIONE


L'idea sviluppata dalla metodologia di risoluzione delle collisioni basato sulla concatenazione consiste nel concatenare a lista i records della tabella mediante un campo puntatore. In altre parole si intende ridurre il fenomeno della agglomerazione concatenando fra loro i records che collidono.
Esistono 2 metodi basati sulla concatenazione: il metodo delle CATENE CONFLUENTI e il metodo delle CATENE DISTINTE.

CLICCA QUI PER ANDARE ALLE CATENE DISTINTE

CLICCA QUI PER ANDARE ALLA FUNZIONE DI REHASHING

(Il metodo a catene confluenti viene qui di seguito)

CATENE CONFLUENTI

I records che collidono vengono collegati fra loro mediante PUNTATORI cioe' aggiungendo ad ogni record un CAMPO LINK che puo' assumere come valore un indirizzo hash (tra quelli generabili) o la codifica del puntatore NULLO LINK. In questo modo costruiamo una GUIDA che ci permette di scandire la lista dei records risolvendo la collisione. Se si raggiunge la fine della lista (link di ultimo record di lista=nil) vuol dire che la chiave cercata non c'e'.

ESEMPIO. Nella tabella, sotto inizialmente vuota, sono state inserite le chiavi FRANCO E LUCA nei corrispondenti indirizzi hash 1 e 4. Supponiamo che la chiave GIANNI collida con FRANCO: il suo inserimento assieme all'indirizzo 0, cioe' nella testa della Lista Libera. La chiave MARCO ha indirizzo 0 che e' pero' occupato da GIANNI: l'inserimento di GIANNI avviene allora nella testa della Lista Libera con conseguente CONCATENAZIONE dall'indirizzo 0 all'indirizzo 2.
In questo caso si e' verificata una confluenza in quanto gli elementi che compongono la lista accessibile da 1 contiene sia records con chiave avente indirizzo hash 1 che records con chiave avente indirizzo hash 0. (NB: LL e' il puntatore alla testa della Lista Libera).

CLICCA QUI PER VEDERE L'ESEMPIO GRAFICO

E' importante sottolineare che la cancellazione di un record qualche problema se il suddetto record appartiene ad una catena: non e' infatti sufficiente restituirlo alla LISTA LIBERA perche' si potrebbero rendere invisibili i records aventi come indirizzo hash l'indirizzo del record cancellato.