4° Anno TEORIA 3. Archivi e file - Page 27

11 : Archivi e file Vers . 2.0 – Dicembre 2020
La gestione delle collisioni
Come abbiamo visto , anche facendo la massima attenzione nella scelta della funzione Hash , è praticamente impossibile evitare le collisioni . Pertanto il prevedere opportune tecniche per la gestione delle collisioni è parte integrante dell ’ intera tecnica Hash .
DEF : Le tecniche di gestione delle collisioni sono metodi che consentono di individuare un indirizzo libero per la chiave k nel caso in cui la funzione Hash H ( k ) restituisca un valore già ottenuto per un ’ altra chiave .
N . B . La gestione corretta di questa specifica situazione è di grande importanza sia in fase di inserimento dei record sia in fase di ricerca di una chiave . (*) In caso di inserimento si applicherà ad ogni chiave uno dei metodi per il calcolo degli indirizzi sopra specificati ( o altri ancora ). Ottenuto il valore si eseguirà un test per controllare se la posizione indicata è occupata ( collisione ) o libera . Se è libera il record può essere inserito ma se è occupata dovrà essere ricercata una nuova posizione , fino a che non se ne incontrerà una libera ; (*) In caso di ricerca si applicherà alla chiave da ricercare uno dei metodi per il calcolo degli indirizzi sopra specificati ( o altri ancora ) e si accederà al record . Se la chiave in esso contenuta coincide con quella cercata , la ricerca termina altrimenti occorrerà scandire l ’ archivio andando su altre posizioni sino a quando non si troverà la chiave cercata .
Esistono vari metodi per la gestione delle collisioni . Esaminiamone alcuni :
a ) Scansione lineare o indirizzamento aperto Tale tecnica consiste nel ricercare il primo posto libero in cui sistemare la chiave che ha generato la collisione , spostandosi all ’ interno dell ’ archivio di un certo numero p di posizioni , detto passo di scansione , fino a quando non si incontra una posizione libera .
Se in particolare p = 1 si parla di scansione lineare con passo unitario . La scelta del passo unitario assicura il controllo su tutti gli indirizzi fino al completamento delle posizioni disponibili nell ’ archivio .
Questo metodo ha l ’ inconveniente di creare lunghe catene di record consecutivi , rallentando il tempo di accesso ai record . Inoltre provoca il fenomeno detto agglomerazione o addensamento primario delle chiavi ( clustering ) ossia la presenza di aree di memoria - agglomerati o cluster – nelle quali confluiscono varie sequenze di sinonimi che presentano indirizzi coincidenti da un certo punto in poi .
Esempio
Supponiamo di dover memorizzare le seguenti chiavi in un archivio composto al massimo da 9
record :
9
28
29
35
24
48
71
64
Per generare gli indirizzi ci serviamo del metodo della divisione modulo 9 . Abbiamo
k = 9
H ( k ) = ( 9 MOD 9 ) + 1 = 0 + 1 = 1
k = 28
H ( k ) = ( 28 MOD 9 ) + 1 = 1 + 1 = 2
k = 29
H ( k ) = ( 29 MOD 9 ) + 1 = 2 + 1 = 3
k = 35
H ( k ) = ( 35 MOD 9 ) + 1 = 8 + 1 = 9
k = 24
H ( k ) = ( 24 MOD 9 ) + 1 = 6 + 1 = 7
k = 48
H ( k ) = ( 48 MOD 9 ) + 1 = 3 + 1 = 4
k = 71
H ( k ) = ( 71 MOD 9 ) + 1 = 8 + 1 = 9
prima collisione
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 27