(Categoria _Structuri de date_, Autor _Catalin Francu_, preluat din cartea _"Psihologia concursurilor de informatica"_)

*TODO:* TOC

(toc){width: 20em}*{text-align:center;} *Continut*
* 'Necesitatea tabelelor hash':tabele-hash-prezentare-detaliata#necesitate
* 'Descrierea structurii':tabele-hash-prezentare-detaliata#descriere
* 'Metoda impartirii cu rest':tabele-hash-prezentare-detaliata#impartire-cu-rest
* 'Metoda inmultirii':tabele-hash-prezentare-detaliata#inmultire
* 'Probleme propuse':tabele-hash-prezentare-detaliata#probleme-propuse
 
h2(#necesitate). Necesitatea tabelelor hash

In multe aplicatii lucram cu structuri mari de date in care avem nevoie sa facem cautari, inserari, modificari si stergeri. Aceste structuri pot fi vectori, matrice, liste etc. In cazurile mai fericite ale vectorilor, acestia pot fi sortati, caz in care localizarea unui element se face prin metoda injumatatirii intervalului, adica in timp logaritmic. Chiar daca nu avem voie sa sortam vectorul, tot se pot face anumite optimizari care reduc foarte mult timpul de cautare. De exemplu, probabil ca multi dintre cititori au idee despre ce inseamna indexarea unei baze de date. Daca avem o baza de date cu patru elemente de tip string, si anume

Pentru imbunatatirea practica a acestui timp sunt folosite _tabelele de dispersie_ sau _tabelele hash_ (engl. hash = a toca, tocatura). Mentionam de la bun inceput ca tabelele hash nu au nicio utilitate din punct de vedere teoretic. Daca suntem rau intentionati, este posibil sa gasim exemple pentru care cautarea intr-o tabela hash sa dureze la fel de mult ca intr-o lista simplu inlantuita, respectiv $O(N)$. Dar in practica timpul cautarii si al adaugarii de elemente intr-o tabela hash coboara uneori pana la $O(1)$, iar in medie scade foarte mult (de mii de ori).

h2(#descriere). Descrierea structurii
 

Iata despre ce este vorba. Sa presupunem pentru inceput ca in loc de pozitii pe tabla de sah, lista noastra memoreaza numere intre 0 si 999. In acest caz, tabela hash ar fi un simplu vector $H$ cu 1000 de elemente booleene. Initial, toate elementele lui $H$ au valoarea $False$ (sau $0$). Daca numarul 473 a fost gasit in lista, nu avem decat sa setam valoarea lui $H(473)$ la $True$ (sau $1$). La o noua aparitie a lui 473 in lista, vom examina elementul $H(473)$ si, deoarece el este $True$, inseamna ca acest numar a mai fost gasit. Daca dorim stergerea unui element din hash, vom reseta pozitia corespunzatoare din $H$. Practic, avem de-a face cu un exemplu rudimentar de ceea ce se cheama functie de dispersie, adica $h(x)=x$. O proprietate foarte importanta a acestei functii este injectivitatea; este imposibil ca la doua numere distincte sa corespunda aceeasi intrare in tabela. Sa incercam o reprezentare grafica a metodei:
!tabele-hash-prezentare-detaliata?hash1.jpg!

Vom termina prin a prezenta doua functii de dispersie foarte des folosite.

h2. Metoda impartirii cu rest

h2(#impartire-cu-rest). Metoda impartirii cu rest

Despre aceasta metoda am mai vorbit. Functia hash este: $h(x) = x mod M$ unde $M$ este numarul de intrari in tabela. Problema care se pune este sa-l alegem pe $M$ cat mai bine, astfel incat numarul de coliziuni pentru oricare din intrari sa fie cat mai mic. De asemenea, trebuie ca $M$ sa fie cat mai mare, pentru ca media numarului de chei repartizate la aceeasi intrare sa fie cat mai mica. Totusi, experienta arata ca nu orice valoare a lui $M$ este buna.

Practic, trebuie ca $M$ sa nu fie un numar rotund in nicio baza aritmetica, sau cel putin nu in bazele 2 si 10. O buna alegere pentru $M$ sunt numerele prime care sa nu fie apropiate de nicio putere a lui 2. De exemplu, in locul unei tabele cu $M=10000$ de intrari, care s-ar comporta dezastruos, putem folosi una cu 9973 de intrari. Chiar si aceasta alegere poate fi imbunatatita; intre puterile lui 2 vecine, respectiv 8192 si 16384, se poate alege un numar prim din zona 11000-12000. Risipa de memorie de circa 1000-2000 de intrari in tabela va fi pe deplin compensata de imbunatatirea cautarii.

h2. Metoda inmultirii

h2(#inmultire). Metoda inmultirii

Pentru aceasta metoda functia hash este $h(x) = [M * {x*A}]$. Aici $A$ este un numar pozitiv subunitar, $0 < A < 1$, iar prin ${x*A}$ se intelege partea fractionara a lui $x*A$, adica $x*A - [x*A]$. De exemplu, daca alegem $M = 1234$ si $A = 0.3$, iar $x = 1997$, atunci avem $h(x) = [1234 * {599.1}] = [1234 * 0.1] = 123$. Se observa ca functia $h$ produce numere intre $0$ si $M-1$. Intr-adevar $0 &le; {x*A} < 1$ <tex>\Rightarrow</tex> $0 &le; M * {x*A} < M$.

            +(B->b_Side << 12)      // 1 bit
            +(B->b_EP << 13)) % M;  // 4 biti

    for (i=0; i<=7; i++)
        for (j=0; j<=7; j++) {
            S = (16*S + B->b_T[i][j]) % M;

    for (i = 0; i <= 7; i++)
        for (j=0; j <= 7; j++) {
            S = (16 * S + B->b_T[i][j]) % M;

        }
    return S;
}
==

h2. Teme pentru acasa

h2(#probleme-propuse). Probleme propuse

Iata si o scurta lista de probleme ce se rezolva eficient folosind tabelele hash: