HASHED FILES
L'idea centrale su cui si basa un hashed files e' la seguente:
data una chiave di ricerca, interviene una FUNZIONE HASH che, trasformando tale chiave in un numero, consente di andare direttamente al record corrispondente.
L'idea e' quella di associare ad ogni chiave con un INDIRIZZO HASH mediante il calcolo di una funzione:
h: S(0,1,2,.......,M-1) (con S l'insieme delle possibili chiavi)
detta appunto FUNZIONE HASH (o funzione di trasformazione della chiave). In un certo senso, tale funzione si prefigge di "estrarre" dalla chiave l'indirizzo dell'elemento contenente o destinato a contenere il record con quella chiave.
Un INDIRIZZO HASH e' un possibile valore dell'indice di un vettore di elementi destinati ad ospitare un record della tabella.
La situazione ideale (TRASFORMAZIONE PERFETTA)si ha quando la funzione h e' INIETTIVA:
per ogni K,K' appartenenti ad S tali che K e' diverso da K' implica che h(k) e'diverso da h(K'),
cioe' ogni chiave ha un suo indirizzo hash distinto da quello di tutte le altre chiavi. In questo caso ogni elemento della tabella puo' essere raggiunto cuon un unico accesso. Perche' cio' sia possibile si richiede che M (il numerodi aree di memoria) sia non minore del numero delle possibili chiavi. Se M e' uguale al numero delle possibili chiavi allora la "trasformazione" si dice MINIMALE. Se il numero massimo delle chiavi che possono essere contemporaneamente presenti nella tabella e' molto inferiore al numero delle possibili chiavi, la trasformazione perfetta comporta un inacettabile spreco di memoria.
In questi casi si rinuncia alla trasformazione perfetta e si accetta il fatto che 2 o piu' chiavi passano "COLLIDERE" cioe' avere lo stesso indirizzo hash:
se M e' minore del numero delle possibili chiavi,
esistono K,K' appartenenti a S tali che h(k)=h(K') (COLLISIONE)
Sorge allora il problema della GESTIONE delle COLLISIONI cioe' dei conflitti che possono nascere quando a piu' chiavi viene attribuito lo stesso indirizzo hash (cioe' piu' records sono memorizzati sulla stessa area di memoria).
CLICCA QUI PER VEDERE COME SI CALCOLA LA PROBABILITA' DI NON COLLISIONE
Il fenomeno delle collisioni richiede un certo numero di accessi supplementari che occorre contenere il piu' possibile. Tale numero dipende, in generale:
a) dalla SCELTA della funzione hash
b) dal METODO utilizzato per RISOLVERE le COLLISIONI