SCELTA DELLA FUNZIONE HASH


Nella scelta della funzione hash occorre rispettare tre esigenze distinte:
a) DISTRIBUZIONE UNIFORME delle chiavi sullo spazio degli indirizzi; occorre cioe' scegliere h in modo che il numero delle chiavi che possono collidere su un indirizzo hash sia approssimativamente lo stesso per ciascuno degli indirizzi hash.
b) DISTRIBUZIONE CASUALE delle chiavi; occorre scegliere h in modo tale che strette correlazioni fra le chiavi (ad esempio: a1,a2,a3 o ire dire udire) non si riflettano in strette correlazioni tra i corrispondenti indirizzi hash..
c) VELOCITA' DI CALCOLO; il tempo richiesto dalla valutazione delloa funzione hash dovrebbe essere trascurabile rispetto a quello di accesso al record.

IMPORTANTE: i primi 2 requisiti costituiscono delle condizioni necessarie per il contenimento del fenomeno delle collisioni e, di conseguenza, del costo richiesti per la loro risoluzione.

ESEMPIO: una delle funzioni hash prese piu' frequentemente in considerazione e' :

h(K)=integer(K)modM

con mod=calcolo del resto intero della divisione fra interi e integer(K) che denota una trsformazione iniettiva della chiave k in un intero. Ad esempio se la chiave e' una stringa, la trasformazione piu' immediata potrebbe essere "l'intero avente come rappresentazione binaria la sequenza dei codici dei caratteri K".
Ad esempio, facendo riferimento alla CODIFICA ASCII, avremo:
integer('ROMA')= 1010010 1001111 1001101 1000001

Ora, il requisito a) e' rispettato se la trasformazione integer e' uniforme in quanto e' noto che l'operatore mod divide gli interi in classi.
Il rispetto del requisito b) e' legato alla scelta di M.
Il requisito c) e' rispettato se l'operazione di mod comporta una divisione fra 2 interi dalla apposita istruzione macchina. Cio' puo' non essere possibile se la chiave e' troppo lunga.

CLICCA QUI SE VUOI ANDARE AL METODO PER RISOLVERE LE COLLISIONI

CLICCA QUI PER RITORNARE ALL'INIZIO