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