FUNZIONE DI REHASHING
Quando 2 o piu' chiavi, dopo la trasformazione della chiave danno lo stesso indirizzo hash si puo' utilizzare un'altra funzione, una FUNZIONE DI REHASHING che RIASSEGNA agli indirizzi hash che collidono degli altri indirizzi. In pratica quando inserisco nel file una chiave con indirizzo hash uguale a quello di un'altra chiave gia' presente, la FUNZIONE REHASHING dara' un altro indirizzo alla chiave inserita per seconda (manterra' lo stesso indirizzo invece la chiave per prima inserita). Faro' lo stesso lavoro ogni volta che un indirizzo hash collide con un altro. La funzione rehashing e' utilizzata ogni volta che devo ricercare l'indirizzo di una chiave che dopo la trasformazione tramite funzione hash collide con un'altra. In altre parole se dopo la funzione hash 2 chiavi hanno lo stesso valore di indirizzo, allora sara' la funzione rehashing che riorganizza le celle dell' area condivisa dalle chiavi con stesso indirizzo hash.
Questo metodo si basa sulla GENERAEZIONE e ISPEZIONE di una sequenza di indirizzi hash (sequenza di scansione) corrispondenti alle celle dell'area condivisa:
a(0),a(1),a(2),a(3),......... (sono accessi supplementari)
definita dal seguente schema:
a(0)=h(K) (indirizzo dell'area condivisa)
a(i+1)=f(i,a(i),K,M) (indirizzi delle singole celle dell'area condivisa)
dove f e' la FUNZIONE REHASHING utilizzata per scandire l'area condivisa. Tale funzione dovrebbe avere la proprieta' di generare una sola volta gli indirizzi hash prima di riprodurre h(K). In altri termini, tramite la funzione f si scandisce l'area condivisa dai dai records aventi lo stesso indirizzo hash (cioe', la trasformazione della chiave K, h(K), origina lo stesso valore) alla ricerca del record di interesse avente cioe' chiave uguale a quella cercata.
CLICCARE QUI PER VEDERE L'ESEMPIO GRAFICO
La scansione di cui si parla si effettua tramite la FUNZIONE REHASHING. In altre parole si generano successivamente gli indirizzi stabiliti dalla funzione rehashing fino a quando non si trova la chiave k cercata oppure quando si puo' concludere che la chiave non c'e' trovando un "postolibero". La legge di scansione piu' semplice e' quella LINEARE CON PASSO UNITARIO:
a(i)=[h(K)+i]modM
In altre parole, si scandiscono sequenzialmente tutte le celle fino a trovare la chiave k cercata o una cella libera.
IMPORTANTE:
La scelta di una funzione di rehashing deve essere molto accurata perche' da essa dipende l'incidenza del fenomeno della AGGLOMERAZIONE tipico dei metodi di indirizzamento aperto. Intuitivamente, un agglomerato e' un insieme di celle occupate da chiavi cui sono associate delle sequenze di scansione coincidenti da un certo punto in poi.
Ad esempio, se la funzione rehashing e' lineare con passo unitario e h[K(0)]=i e h[K(1)]=i+c, la sequenza di scansione di K(0) coincide ("e' situata sopra") a quella di K(1) a partire dal c-esimo indirizzo generato:
sequenza per k(0): i,i+1,i+2,.......,i+c,i+c+1,i+c+2,......,i+c+n
sequenza per K(1): i+c,i+c+1,i+c+2,......,i+c+n,i+c+n+1,i+c+n+2,......,i+c+n+z
La conseguenza di cio' e': i gruppi C1 e C2 aventi rispettivamente indirizzo hash h[K(0)] e h[K(1)] sono sovrapposti per la parte di sequenze evidenziate.
Dalla rappresentazione si vede che i gruppi sono separati da un'unica cella libera di indirizzo X. Se viene inserito una qualsiasi chiave di indirizzo hash compreso X e h[K(1)], la cella X sara' occupata con la conseguenza di "fondere" i gruppi C1 e C2 dando cosi' luogo ad un unico agglomerato C3.
In questo caso il tempo di inserimento e di ricerca (con insuccesso) di chiavi con indirizzo hash compreso tra h[K(1)] e X viene aumentato di un numero di accessi pari al numero delle chiavi di C2.
CLICCARE QUI PER VEDERE L'ESEMPIO GRAFICO
Si osservi che il metodo di indirizamento aperto pone qualche problema nei confronti dell'operazione di cancellazione di un record. Infatti non si puo' pensare di eseguire la CANCELLAZIONE semplicentemente con l'assegnamento:
a(i)=rec(K)<--"posto libero"
perche' essa avrebbe l'effetto di interrompere le sequenze di scansione passanti per i. Una soluzione molto semplice consiste (quando pero' viene cancellato solo un numero esiguo di records) nel lasciare occupata la cella agli effetti della scansione inserendovi un'apposita chiave riservata (=CANCELLAZIONE LOGICA);
ad esempio: a(i)=rec(K)<--"cancellato".
In questo modo, quando la sequenza di scansione incontra un record cancellato, la scansione continua come se il record fosse occupato.
Se invece le cancellazioni avvengono frequentemente puo' essere necessario procedere periodicamente ad una completa riorganizzazione di tutta la tabellla sia per ricopiare lo spazio occupato dai records cancellati sia per ridurre l'incidenza del fenomeno di agglomerazione.
CLICCA QUI PER ANDARE ALLA RISOLUZIONE DELLE COLLISIONE TRAMITE CONCATENAZIONE
CLICCA QUI PER ANDARE A HASHED FILES
