11 : Archivi e file Vers . 2.0 – Dicembre 2020
Per questo caso si opta per funzioni che garantiscono una associazione molti-a-uno ossia può accadere che due o più chiavi in fase di trasformazione possano generare lo stesso indirizzo . Si generano delle collisioni che devono essere risolte predisponendo opportune procedure che collochino le registrazioni in conflitto dette sinonimi in record aventi indirizzo diverso . Quindi possiamo formulare un ulteriore requisito che afferma che una funzione Hash ottimale deve :
7 ) generare il minor numero possibile di collisioni e definisca apposite procedure per l ’ allocazione dei sinonimi ( gestione delle collisioni ).
Avendo capito che è quasi impossibile realizzare funzioni Hash che realizzino la trasformazione perfetta e che quindi esisterà sempre un problema di gestione delle collisioni , occorre concentrarsi sullo sviluppo di funzioni Hash efficienti e non perfette .
Metodi di calcolo degli indirizzi Esistono molti metodi per calcolare gli indirizzi . Esaminiamone alcuni :
a ) Metodo del troncamento Viene utilizzato quando la chiave numerica è composta da un elevato numero di cifre ed il numero di record che possono essere memorizzati è abbastanza limitato . Esso consiste nell ’ estrarre dalla chiave un sottoinsieme di cifre che rappresentano l ’ indirizzo .
Esempio : Supponiamo di avere un archivio contenente i tesserati di una palestra e sul quale possono essere inseriti 1000 record . La chiave primaria è il numero di tessera che è un numero di 7 cifre . Costruiamo la nostra funzione Hash in questo modo : detto x il numero di tessera ( chiave primaria originale ) costituito da 7 cifre , la sua trasformazione prevede l ’ associazione di un numero da 000 a 999 ( indirizzo logico del record nell ’ archivio ) costituito dalle ultime 3 cifre di detta chiave aumentato però di una unità H ( 1543423 ) + 1 = 424 H ( 2325675 ) + 1 = 676 H ( 2320001 ) + 1 = 002 H ( 6885675 ) + 1 = 676
Vantaggi : è un metodo molto efficiente in cui le chiavi numeriche siano principalmente consecutive e con poche interruzioni
Svantaggi : è un metodo che produce sinonimi ogni volta che si incontrano chiavi aventi le ultime 3 cifre uguali . Inoltre richiede spesso che l ’ archivio debba essere composto da un numero di record superiore a quanto necessario .
Applichiamo questo metodo ad una chiave alfanumerica . Esempio : Supponiamo che la chiave da trasformare debba essere composta da 4 caratteri estratti dagli ultimi 4 della chiave primaria Per procedere alla trasformazione si può procedere come segue : poniamo in corrispondenza le 26 lettere dell ’ alfabeto con i primi 26 numeri naturali seguendo l ’ ordine alfabetico ( A = 0 , B = 1 ; … Z = 25 ). A questo punto come nei sistemi di numerazione pesati si converte la sottostringa formata dagli ultimi 4 caratteri applicando una sorta di conversione in base 26 . H ( HELLOCIAO ) = ( CIAO ) 26 = C x 26 3 + I x 26 2 + A x 26 1 + O x 26 0 = 40574
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 25