Hash table: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 24:
Se una pagina bucket primaria è piena viene creata una pagina di overflow. Per cercare l'etichetta corrispondente alla chiave k (M = numero di bucket) si utilizza la seguente formula di [[hash]]
h(k) = bucket a cui appartiene l'etichetta.
La funzione di hash ''h'' agisce sul campo della chiave di ricerca del record r e deve distribuire i valori su 0,...,M-1 (M bucket). Le prestazioni della ricerca dipendono molto dalla funzione h.
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===
h(chiave) = (a * chiave + b) mod M (dove a e b sono costanti)
== Hashing estendibile ==
| |||