Hash table: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 37:
Nell'hashing estendibile si parla di profondità di directory e si intende il numero minimo di bit che permette di rappresentare il numero di elementi contenuti nella directory.
== Hashing
L'hashing lineare, come accenato nel paragrafo precendente, 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 h0,h1,... hn dove hi ha un range che è la metà di quello di hi+1. Questo vuol dire che il range di h1 è 2^1 N
Se N = 32 allora il numero minino di bit per la rappresentazione del numero è 5. Quindi h0 = h mod 2^0 N cioè h0 = h mod 32
La prossima funzione h2 avrà range 5 + 1 e potrà rapprensetare i bucket da 0 a 63. La funzione di hash sarà come segue h1 = h mod 2 ^ 1 * 32
| |||