h3. Double hashing-ul lui Mihai Patrascu

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$.

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 statici de dimensiune $4$.

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