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

11 : Archivi e file Vers . 2.0 – Dicembre 2020
A questo punto per ottenere il reale indirizzo si può applicare il metodo del troncamento avendo però stabilito a priori il numero massimo di record dell ’ archivio .
Svantaggi : è un metodo che produce sinonimi ogni volta che si incontrano chiavi che terminano con le stesse 4 lettere . Inoltre anche in questo caso si richiede che l ’ archivio sia composto da un numero di record superiore a quanto necessario .
b ) Metodo di folding ( dall ’ inglese “ piegare ”) Questo metodo consiste nel dividere la chiave numerica in due o più parti . Successivamente tali parti vengono sommate tra loro ed il valore ottenuto ( o una sua parte ) viene utilizzato come indirizzo .
Esempio : Supponiamo di volere trasformare la chiave 563710 secondo questo metodo .
5 6 3 7 1 0
ossia
3 6 5
7 1 0
+
H ( 563710 ) = 365 + 710 = 1075
Anche questo metodo genera collisioni ( H ( 349132 ) e presenta gli stessi svantaggi del metodo di troncamento .
c ) Metodo della divisione modulo n Questo metodo consiste nell ’ assegnare come indirizzo del record il resto della divisione della chiave numerica per il numero massimo di record memorizzabili nell ’ archivio .
In generale detta k la chiave e detto N il numero massimo di record contenuti nell ’ archivio , l ’ indirizzo del record sarà dato dalla trasformazione :
H ( k ) = ( k MOD N ) + 1 (*)
(*) Il “ più 1 ” è giustificato dal fatto che come sappiamo l ’ operatore modulo fornisce sempre valori compresi tra 0 ed N-1 e quindi anche gli indirizzi sarebbero compresi in tale intervallo . Con l ’ aggiunta dell ’ unità tale intervallo si trasforma nell ’ intervallo [ 1 , N ].
Anche questo metodo genera sinonimi e per ridurre la loro presenza è fondamentale la scelta dell ’ N . Tale metodo ha però il vantaggio di poter essere applicato anche in presenza di un numero massimo di record che non sia multiplo di 10 . Inoltre gli indirizzi generati , a causa del significato dell ’ operatore modulo , non necessitano di troncamento .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 26