Hash table: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 32:
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.
== Hashing
Sostanzialmente è un miglioramento dell'hashing statico, perché oltre ad inserire bucket di overflow permette di raddoppiare il numero di bucket e di riorganizzare le etichette.
L'unico problema sta nella riorganizzazione delle etichette, dato che questa operazione è costosa in termini di tempo. Esistono due soluzioni. La prima (hashing estendibile) gestisce una directory di puntatori ai bucket primari, la seconda (hashing lineare) permette di risolvere il problema senza l'utilizzo delle directory ma con una famiglia di funzioni hash.
|