Hash table: differenze tra le versioni

Versione delle 00:00, 23 ago 2011

Versione delle 16:58, 22 set 2011

Riga 25:

Nell'hashing statico si utilizza il concetto di bucket, che è l'insieme di pagine contenenti le etichette dei record di dati.

Se una pagina bucket primaria è piena, viene creata una pagina di overflow. Per cercare l'etichetta corrispondente alla chiave <math>k</math> (<math>M =</math> numero di bucket) si utilizza la seguente formula di [[hash]]

<math>h(k) = \mbox{bucket}</math> a cui appartiene l'etichetta.

La funzione di hash <math>h</math> agisce sul campo della chiave di ricerca del record <math>r</math> e deve distribuire i valori su <math>0,...,M-1</math> (<math>M</math> bucket). Le prestazioni della ricerca dipendono molto dalla funzione <math>h</math>.

Riga 41:

== Hashing lineare ==

L'hashing lineare, come accennato nel paragrafo precedente, permette di risolvere il problema delle lunghe catene di overflow senza l'utilizzo delle directory.

L'idea di base è quella di utilizzare una famiglia di funzioni hash <math>h_0,h_1,... h_n</math> dove hi<math>h_i</math> ha un range che è la metà di quello di <math>h_i+1</math>. Questo vuol dire che il range di <math>h_1</math> è <math>2^1 N</math>

=== Esempio ===

Se <math>N=32</math> allora il numero minino di bit per la rappresentazione del numero è 5. Quindi <math>h_0 = h \bmod 2^0 N</math> cioè <math>h_0 = h \bmod 32</math>

La prossima funzione <math>h_2</math> avrà range <math>5+1</math> e potrà rapprensetarerappresentare i bucket da 0 a 63. La funzione di hash sarà come segue <math>h_1 = h \bmod 2 ^ 1 * 32</math>

==Bilanciamento spazio/tempo==

Riga 63:

==Analisi del costo di scansione==

Il numero di passi adda effettuare per una scansione completa della tabella è data nel caso medio da:

{| border=1 cellspacing=1 align="center" cellpadding="1"