Originariamente inviato da Neptune
Quindi un "hash" sarebbe una specie di indice di riga, ma può esserci che per quella riga ci siano più elementi, ovvero "più colonne" (se vogliamo rappresentare tutto come una tabella) e quindi scorriamo nella linked list per trovare l'elemento che realmente stavamo cercando facendo un confronto tra gli indici "di pagina logica" a cui poi assocerà la pagina fisica?
Esattamente.
E questo metodo dovrebbe essere più veloce di una "normale tabella di allocazione dei pocessi" ? (anche se in realtà non saprei definire come viene in realtà memorizzata una tabella non di tipo hash)
Bisognerebbe capire cos'è una "normale tabella".

Se è un normale array, ci sono i costi di ridimensionamento (a meno che non lo si renda di dimensione fissa e finita lì) e la ricerca non è immediata, a meno che non si tenga l'array ordinato (costi aggiuntivi), nel qual caso si può usare una ricerca binaria, oppure si usi un array di dimensione fissa e massima, e accedi agli elementi usando direttamente il numero di pagina logica.

Il problema è che, se su macchine a 32 bit questo è fattibile, su macchine a 64 bit la questione diventa più complicata: supponiamo di avere una macchina che può indirizzare 4 GiB di memoria fisica, divise in pagine da 4 KiB; abbiamo quindi 1048576 pagine. Servono quindi 1048576 ingressi di tabella; per un semplice mapping pagina logica->pagina fisica basterebbero interi a 20 bit, con cui però è scomodo lavorare, per cui diciamo che usiamo normali interi a 32 bit, in modo da avere anche 12 bit per memorizzare gli attributi delle pagine logiche.
Ora, ci serve una tabella da 1048576 ingressi ciascuno di 4 byte, ossia 4 MB di memoria, una cosa fattibilissima con un normale array.

Ma pensiamo ora ad una macchina a 64 bit, in cui è possibile indirizzare 2^64 byte di memoria fisica: se anche usassimo pagine da 4 MiB, si tratterebbe comunque di 2^64/2^22=2^42 voci di tabella, che, anche usando interi a 48 bit, necessiterebbero, per il modello ad array "normale", di 3*2^42 byte, ossia di 24 TiB di spazio per la sola tabella di mapping logico-fisico.

Una soluzione quindi possono essere le tabelle multilivello: una tabella "master" da 2^21 ingressi, uno per ciascun blocco di 2^21 byte; ogni ingresso contiene un puntatore ad un'altra tabella da 2^21 ingressi, ognuno dei quali è relativo ad una pagina da 4 MiB. Naturalmente le tabelle "secondarie" vengono allocate solo se necessario.

Un'altra soluzione invece è appunto la tabella di hash, basta dimensionarla all'inizio in maniera adeguata alla memoria fisica da gestire (un tot più grande del necessario se si prediligono le prestazioni, un po' più piccola se si può accettare un numero di collisioni più alto a patto di un ingombro inferiore in memoria).

Nota: se stai preparando un esame su questa roba, controlla anche altrove quello che sto dicendo, dato che non ho mai studiato seriamente informatica, mi baso giusto su una lettura "di piacere" dal Tanenbaum e sul buon senso.