Hash table: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Fabior1984 (discussione | contributi)
Esempio di funzione hash: funzione modulo in tex
Fabior1984 (discussione | contributi)
Hashing lineare: trascrivo le funzioni in tex
Riga 38:
== Hashing lineare ==
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<math>h_0,h1h_1,... hnh_n</math> dove hi ha un range che è la metà di quello di hi<math>h_i+1</math>. Questo vuol dire che il range di h1<math>h_1</math> è <math>2^1 N</math>
=== Esempio ===
Se <math>N = 32</math> allora il numero minino di bit per la rappresentazione del numero è 5. Quindi h0<math>h_0 = h mod\bmod 2^0 N</math> cioè h0<math>h_0 = h mod\bmod 32
La prossima funzione h2<math>h_2</matg> avrà range <math>5 + 1</math> e potrà rapprensetare i bucket da 0 a 63. La funzione di hash sarà come segue h1<math>h_1 = h mod\bmod 2 ^ 1 * 32</math>
 
==Bilanciamento spazio/tempo==