11 : Archivi e file Vers . 2.0 – Dicembre 2020
B ) L ’ ORGANIZZAZIONE HASH La tecnica HASH si basa sull ’ utilizzo di funzioni che , partendo dalla chiave primaria di ciascun record , trasformano quest ’ ultima in un numero intero che rappresenta l ’ indirizzo logico detto indirizzo hash del record stesso .
In generale applicare la tecnica Hash significa definire una funzione di randomizzazione H ( funzione di Hash ) che associ ad ogni record l ’ indirizzo di un record logico in cui è possibile memorizzarlo , attraverso la trasformazione della chiave K in un intero x compreso tra 1 ed N dove N è il numero di indirizzi logici a disposizione .
In altre parole
H ( K ) = x
L ’ indirizzo x deve essere calcolato tutte le colte che occorre accedere al record per effettuare operazioni di I / O .
Archivio
Chiave primaria
Funzione di Hash indirizzo
Rec1 Rec2 …… Rec100
La funzione Hash La scelta della funzione Hash è importantissima perché una funzione di trasformazione non idonea può rendere inefficiente o completamente invalida tutta l ’ organizzazione stessa .
Una funzione Hash ottimale deve :
1 ) essere facilmente calcolabile ossia essere composta da calcoli facili in modo da non appesantire il tempo di accesso ; 2 ) produrre sempre lo stesso indirizzo a partire dalla stessa chiave ( deterministica ); 3 ) generare indirizzi uniformemente distribuiti nell ’ ambito dell ’ archivio ; 4 ) generare indirizzi casualmente distribuiti nell ’ ambito dell ’ archivio , relativamente alle chiavi simili ( Es . di chiavi simili X1 , X2 , X3 oppure DARE , MARE ; CARE ); 5 ) cercare di coprire l ’ intero intervallo degli indirizzi evitando , se possibile , che vi siano indirizzi mai generati ; 6 ) generare indirizzi diversi se le chiavi sono diverse ; Quindi secondo questo punto la funzione Hash ideale è quella che ad ogni valore della chiave associ sempre un indirizzo diverso in modo che ogni record possa essere raggiunto tramite un solo accesso ( trasformazione perfetta ) Questo è ben lontano dalla realtà in quanto è molto difficile generare funzioni Hash che consentano una corrispondenza uno-a-uno tra chiave ed indirizzo . Infatti questo tipo di associazioni : - richiedono che il numero di record dell ’ archivio fisico sia uguale al numero dei possibili valori che la chiave può assumere ; - comportano un notevole spreco di memoria e quindi una inefficienza generale del sistema perché in generale il numero di chiavi effettive da gestire è sensibilmente minore rispetto al numero di chiavi ipotetiche .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 24