* Memorie: $O(N)$
* Pointeri: NU

h3. Mihai Patrascu's Double hashing

h3. Double hashing-ul lui Mihai Patrascu

O imbunatarire foarte mare la tabela de hashing este... inca o tabela de hashing. Vom avea $2$ tabele, fiecare cu propria ei functie de hash, iar coliziunile le rezolvam prin inlantuire; cand inseram un element il vom adauga in tabela in care intra intr-un lant mai scurt. Cautarea se face in ambele tabele in locatiile returnate de cele $2$ functii de hash; stergerea la fel. Astfel, lungime celui mai lung lant va fi, in medie, {$lg(lg(N))$}. Dar, in practica, lungimea unui astfel de lant nu va depasi $4$ elemente, pentru ca cel mai mic $N$ pt care $lg(lg(N)) = 5$ este {$2^32^$ ~ 2.000.000.000$}!!! Deci in loc de liste folosim vectori statice de dimensiune 4.

O imbunatatire foarte mare la tabela de hashing este... inca o tabela de hashing. Vom avea 2 tabele, fiecare cu propria ei functie de hash, iar coliziunile le rezolvam prin inlantuire; cand inseram un element, il vom adauga in tabela in care intra intr-un lant mai scurt. Cautarea se face in ambele tabele in locatiile returnate de cele 2 functii de hash; stergerea la fel. Astfel, lungimea celui mai lung lant va fi, in medie, {$lg(lg(N))$}. Dar, in practica, lungimea unui astfel de lant nu va depasi $4$ elemente, pentru ca cel mai mic $N$ pentru care $lg(lg(N)) = 5$ este {$2^32^ ~ 4.000.000.000$}!!! Deci, in loc de liste folosim vectori statice de dimensiune $4$.

* Memorie: {$O(N)$}, pointeri: nu

* Memorie: $O(N)$
* Pointeri: NU

h2. Functii de hash

h3. Pentru numere intregi:

p(pre).
* h(x) = x {@%@} M
* h(x) = (x * r) % M , r - numar aleator ales la inceputul programului

* $h(x) = x % M$
* {$h(x) = (x * r) % M$}, $r$ - numar aleator ales la inceputul programului
 
h3. Pentru numere reale
 
* {$h(x) = [ {A * x} * M ]$}, $0 < A < 1$
 
${x}$ - partea fractionara a lui $x$
$[x]$ = partea intreaga a lui $x$
$[x] + {x} = x$ - prin definitie
$A$ este un numar care trebuie ales inainte sau la inceputul rularii programului. Alegerea lui influenteaza eficienta functiei. Knuth propune valoarea <tex>A = \frac{(\sqrt{5}-1)}{2} \approx 0.6180339887...</tex>
 
 

h3. Pentru adresarea directa

* h(x , i) = ( h1(x) + i * h2(x) ) {@%@} M
r1, r2 - numere alese aleator la inceputul programului.

h3. Pentru numere reale
 
p(pre).
* h(x) = [ {a * x} * M ] , 0 < a < 1
 
${x}$ - partea fractionara a lui {$x$}
$[x]$ = partea intreaga a lui {$x$};
$[x] + {x} = x$ - prin definitie;
$a$ este un numar care trebuie ales inainte sau la inceputul rularii programului; alegerea lui influenteaza eficienta functiei; Knuth propune urmatoarea valoare pentru $a=(sqrt(5)-1)/2$ ~ {$0.6180339887$}...
 

h2. Teme pentru acasa
Incercati sa rezolvati urmatoarele probleme: