h1. Tabele hash - scurta prezentare

(Categoria _Structuri de date_, Autor _Mihnea Giurgea_)

(Categoria _Structuri de date_, Autor _Giurgea Mihnea_)

(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)

h2. 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). Adresare directa

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

h2(#standard_hashing). Standard hashing

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

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

Cum rezolvam coliziunile?

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

h2(#functii). Functii de hash

h2. 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^$}.

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

h2(#concluzie). In loc de concluzie

h2. Teme pentru acasa (TODO: mutare in articolul din Francu)
 
Incercati sa rezolvati urmatoarele probleme:
 
* "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

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.

TODO: de fixat toate link-urile din site care trimiteau la articolul asta

3687