Hash table: differenze tra le versioni

Versione delle 12:25, 28 nov 2009

Versione delle 12:27, 28 nov 2009

Riga 22:

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]]

h(k) = bucket 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>.

Le pagine di bucket primarie, nell'hashing statico, sono allocate consecutivamente. Questo può portare ad avere il problema di lunghe catene di overflow che degradano le prestazioni dato che non abbiamo pagine contigue.

===Esempio di funzione hash===

<math>h(chiave) = (a * chiave + b) mod M</math> (dovecon <math>a</math> e <math>b sono</math> costanti)

== Hashing estendibile ==