h1. Tabele hash - scurta prezentare
(Categoria _Structuri de date_, Autor _Giurgea Mihnea_)
(Categoria _Structuri de date_, Autor _Mihnea Giurgea_)
h2. Scopul tabelelor de dispersie (hash tables)
(toc){width: 20em}*{text-align:center;} *Continut*
* 'Scopul tabelelor de dispersie':tabele-hash-scurta-prezentare#scop
* 'Adresare directa':tabele-hash-scurta-prezentare#adresare_directa
* 'Standard hashing':tabele-hash-scurta-prezentare#standard_hashing
* 'Functii de hash':tabele-hash-scurta-prezentare#functii
* 'In loc de concluzie':tabele-hash-scurta-prezentare#concluzie
h2(#scop). Scopul tabelelor de dispersie (hash tables)
Ne propunem sa cream o structura de date eficienta care sa poata face urmatoarele operatii cat mai repede posibil: _Insereaza_, _Cauta_ si _Sterge_. Ideea din spatele hashing-ului este memorarea unui element intr-un tablou sau lista, in functie de cheia sa. Pe cazul mediu toate aceste operatii necesita $O(1)$ timp. Sa vedem cum:
h2. Adresare directa
h2(#adresare_directa). Adresare directa
Elementele sunt puse intr-un tablou alocat static pe pozitiile cheilor lor. Prin adresare directa, un element cu cheia $k$ va fi memorat in locatia {$k$}. Toate cele $3$ operatii sunt extrem de simple(necesita doar o accesare de memorie), dar dezavantajul este ca aceasta tehnica "mananca" foarte multa memorie: {$O(|U|)$}, unde $U$ este universul de chei.
Elementele sunt puse intr-un tablou alocat static pe pozitiile cheilor lor. Prin adresare directa, un element cu cheia $k$ va fi memorat in locatia $k$. Toate cele 3 operatii sunt extrem de simple (necesita doar o accesare de memorie), dar dezavantajul este ca aceasta tehnica "mananca" foarte multa memorie: $O(|U|)$, unde $U$ este universul de chei.
h2. Standard hashing
h2(#standard_hashing). Standard hashing
Primul pas in a rezolva problema memoriei este de a folosi $O(N)$ memorie in loc de {$O(|U|)$}, unde $N$ este numarul de elemente adaugate in hash. Astfel, un element cu cheia $k$ nu va fi memorat in locatia {$k$}, ci {$h(k)$}, unde {@h:U->{0,1,...,N-1}@} - o functie aleasa aleator, dar determinista( $h(x)$ va returna mereu aceeasi valoare in cursul rularii unui program ). Daca functia este aleasa aleator, elementele vor fi "imprastiate" in hash in mod echivalent, egal. Ideal ar fi ca fiecare element sa fie stocat in locatia lui. Acest lucru insa nu este posibil, pentru ca $N < |U|$ si, deci, de multe ori mai multe elemente vor fi repartizate in aceeasi locatie. Aceasta problema se numeste coliziune.
Primul pas in a rezolva problema memoriei este de a folosi $O(N)$ memorie in loc de $O(|U|)$, unde $N$ este numarul de elemente adaugate in hash. Astfel, un element cu cheia $k$ nu va fi memorat in locatia $k$, ci $h(k)$, unde $h: U -> {0, 1, ..., N-1}$ - o functie aleasa aleator, dar determinista ({$h(x)$} va returna mereu aceeasi valoare pentru un anumit $x$ in cursul rularii unui program). Daca functia este aleasa aleator, elementele vor fi "imprastiate" in hash in mod egal. Ideal ar fi ca fiecare element sa fie stocat singur in locatia lui. Acest lucru insa nu este posibil, pentru ca $N < |U|$ si, deci, de multe ori mai multe elemente vor fi repartizate in aceeasi locatie. Aceasta problema se numeste coliziune.
Cum rezolvam coliziunile?
h3. Inlantuire
In fiecare locatie din hash tinem o lista inlantuita; astfel, la oricare din cele $3$ operatii se va parcurge toata lista. Pe un caz pur teoretic, toate cele $N$ elemente ar putea fi repartizate in aceeasi locatie, insa pe cazuri practice lungimea medie a celui mai lung lant este de {$lg(N)$}.
In fiecare locatie din hash tinem o lista inlantuita; astfel, la oricare din cele 3 operatii se va parcurge toata lista. Pe un caz pur teoretic, toate cele $N$ elemente ar putea fi repartizate in aceeasi locatie, insa pe cazuri practice lungimea medie a celui mai lung lant este de {$lg(N)$}.
* Memorie: {$O(N)$}, pointeri: da
* Memorie: $O(N)$
* Pointeri: DA
h3. Liste statice
Aceasta metoda este o imbunatatire a punctului anterior: pentru ca lungimea unui lant este cel mult {$lg(N)$}, putem sa folosim, in loc de liste inlantuite, vectori alocati dinamic de lungime $lg(N)$ - sau {$lg(N) + 3$}, ca sa fiti siguri :). Scapam astfel de lucrul cu pointerii.
Aceasta metoda este o imbunatatire a punctului anterior: pentru ca lungimea unui lant este cel mult {$lg(N)$}, putem sa folosim, in loc de liste inlantuite, vectori alocati dinamic de lungime $lg(N)$ - sau {$lg(N) + 3$}, ca sa fim siguri :). Scapam astfel de lucrul cu pointerii.
* Memorie: {$O(N*lg(N))$}, pointeri: nu
* Memorie: $O(N*lg(N))$
* Pointeri: NU
h3. Adresare directa
h3. Adresare deschisa
Prin adresare directa, toate elementele sunt memorate in tabela de hash. Pentru a realiza operatiile cerute, verificam succesiv tabela de hash pana cand fie gasim o locatie libera(in cazul Inserarii), fie gasim elementul cautat (pentru {@Cauta@}, {@Sterge@}). Insa, in loc sa cautam tabela de hash in ordinea {$0,1,....,N-1$}, sirul de pozitii examinate depinde de cheia ce se insereaza. Pentru a determina locatiile corespunzatoare, extindem functia de hash astfel incat sa contina si numarul de verificare ca un al doilea parametru {@h:U*{0,1,....,N-1}->{0,1,...,N-1}@}. Astfel, cand vom insera un element, verificam mai intai locatia {$h(k , 0)$}, apoi {$h(k , 1)$} etc. Cand ajungem sa verificam {$h(k , N)$} putem sa ne oprim pentru ca tabela de hash este plina; pentru cautare aplicam aceeasi metoda; daca ajungem la {$h(k , N)$} sau la o pozitie goala inseamnca ca elementul nu exista. Stergerile se fac insa mai greu, pentru ca nu se poate "sterge" pur si simplu un element deoarece ar strica tot hash-ul; in schimb, se marcheaza
locatia ce trebuie stearsa cu o valoare $STERS$ si se modifica functia Insereaza astfel incat sa vada locatiile cu valoarea $STERS$ ca pozitii goale.
Prin adresare deschisa, toate elementele sunt memorate in tabela de hash. Pentru a realiza operatiile cerute, verificam succesiv tabela de hash pana cand fie gasim o locatie libera (in cazul _Inserarii_), fie gasim elementul cautat (pentru _Cauta_, _Sterge_). Insa, in loc sa cautam tabela de hash in ordinea $0, 1, ..., N-1$, sirul de pozitii examinate depinde de cheia ce se insereaza. Pentru a determina locatiile corespunzatoare, extindem functia de hash astfel incat sa contina si numarul de verificare ca un al doilea parametru $h: U * {0, 1, ..., N-1} -> {0, 1, ..., N-1}$. Astfel, cand vom insera un element, verificam mai intai locatia {$h(k, 0)$}, apoi {$h(k, 1)$} etc. Cand ajungem sa verificam {$h(k, N)$} putem sa ne oprim pentru ca tabela de hash este plina. Pentru cautare aplicam aceeasi metoda; daca ajungem la {$h(k, N)$} sau la o pozitie goala, inseamna ca elementul nu exista. Stergerile se fac insa mai greu, pentru ca nu se poate "sterge" pur si simplu un element deoarece ar strica tot hash-ul. In schimb, se marcheaza locatia ce trebuie stearsa cu o valoare $STERS$ si se modifica functia _Insereaza_ astfel incat sa vada locatiile cu valoarea $STERS$ ca pozitii goale.
* Memorie: {$O(N)$}, pointeri: nu
* 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 statici de dimensiune $4$.
* Memorie: {$O(N)$}, pointeri: nu
* Memorie: $O(N)$
* Pointeri: NU
h2. Functii de hash
h2(#functii). Functii de hash
Toate functiile de hash intorc un numar intre $0$ si {$M-1$}, unde $M$ este dimensiunea maxima a tabelei de hash. Este recomandat ca $M$ sa fie ales un numar prim si sa se evite alegerea lui {$M=2^k^$}.
h3. Pentru numere intregi:
p(pre).
* h(x) = x {@%@} M
* h(x) = (x * r) % M , r - numar aleator ales la inceputul programului
h3. Pentru adresarea directa
p(pre).
* h(x , i) = ( h'(x) + i ) {@%@} M
* h(x , i) = ( h'(x) + r1 * i + r2 * i^2^ ) {@%@} M
* h(x , i) = ( h1(x) + i * h2(x) ) {@%@} M
r1, r2 - numere alese aleator la inceputul programului.
* $h(x) = x % M$
* {$h(x) = (x * r) % M$}, $r$ - numar aleator ales la inceputul programului
h3. Pentru numere reale
p(pre).
* h(x) = [ {a * x} * M ] , 0 < a < 1
* {$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$}...
${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>
h2. Teme pentru acasa
h3. Pentru adresarea deschisa
Incercati sa rezolvati urmatoarele probleme:
* $h(x, i) = (h'(x) + i) % M$
* $h(x, i) = (h'(x) + r1 * i + r2 * i^2^) % M$
* $h(x, i) = (h1(x) + i * h2(x)) % M$
$r1$, $r2$ - numere alese aleator la inceputul programului.
* "Magic Pairs":http://acm.sgu.ru/problem.php?contest=0&problem=119
* "Walls":http://acm.sgu.ru/problem.php?contest=0&problem=174
* "Algoritmus 3 - 3: Colinearitate":http://www.algoritmus.org/probleme/probleme_runda03.php
h2(#concluzie). In loc de concluzie
TODO: de fixat toate link-urile din site care trimiteau la articolul asta
Desi o tabela hash poate fi implementata in diverse moduri (cu pointeri sau fara, cu mai multa sau mai putina memorie etc), nu pentru toate situatiile e la fel de usor de ales o functie eficienta. Implementarile mai complexe necesita mai multe sapaturi dupa functii bune. Iar de multe ori se prefera implementari concise si clare in locul celor stufoase care maresc eficienta, dar nu suficient. De aceea, cel mai frecvent mod de tratare al coliziunilor ramane inlantuirea. Mai multe detalii despre acesta, precum si anumite precizari despre cum sa alegi o functie hash buna in cazul diverselor tipuri de date, gasiti in articolul 'Tabele hash - prezentare detaliata':tabele-hash-prezentare-detaliata preluat din cartea "Psihologia concursurilor de informatica" a lui Catalin Francu. In acelasi articol gasiti si o lista de aplicatii pentru aceasta structura de date eficienta.
