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

$B = ( "bac", "zugrav", "abac", "zarva")$

$B = ("bac", "zugrav", "abac", "zarva")$

putem construi un vector $Ind$ care sa ne indice ordinea in care s-ar cuveni sa fie asezate cuvintele in vectorul sortat. Ordinea alfabetica (din cartea de telefon) a cuvintelor este: "abac", "bac", "zarva", "zugrav", deci vectorul Ind este:

putem construi un vector $Ind$ care sa ne indice ordinea in care s-ar cuveni sa fie asezate cuvintele in vectorul sortat. Ordinea alfabetica (din cartea de telefon) a cuvintelor este: "abac", "bac", "zarva", "zugrav", deci vectorul $Ind$ este:

$Ind = (3, 1, 4, 2)$

semnificand ca primul cuvant din vectorul sortat ar trebui sa fie al treilea din vectorul $B$, respectiv "abac" si asa mai departe. In felul acesta am obtinut un vector sortat, care presupune o indirectare a elementelor. Vectorul sortat este

semnificand ca primul cuvant din vectorul sortat ar trebui sa fie al treilea din vectorul $B$, respectiv "abac", si asa mai departe. In felul acesta am obtinut un vector sortat, care presupune o indirectare a elementelor. Vectorul sortat este

$B' = (B(Ind(1)), B(Ind(2)), B(Ind(3)), B(Ind(4))$.

sfarsit
==

Nu vom insista asupra a cum se expandeaza o pozitie si cum se calculeaza efectiv cea mai buna mutare. Noi ne vom interesa de un singur aspect, si anume cautarea unei pozitii in lista. Tehnica cea mai "naturala" este o parcurgere a listei de la cap la coada, comparand pe rand pozitia cautata cu fiecare pozitie din lista. Daca lista are memorate N pozitii, atunci in cazul unei cautari cu succes (pozitia este gasita), numarul mediu de comparatii facute este $N/2$, iar numarul cel mai defavorabil ajunge pana la $N$. In cazul unei cautari fara succes (pozitia nu exista in lista), numarul de comparatii este intotdeauna $N$. De altfel, cazul cautarii fara succes este mult mai frecvent pentru problema jocului de sah, unde numarul de pozitii posibile creste expnumarul mediu de comparatii facute este $N/2$, iar numarul cel mai defavorabil ajunge pana la $N$. In cazul unei cautari fara succes (pozitia nu exista in lista), numarul de comparatii este intotdeauna $N$. De altfel, cazul cautarii fara succes este mult mai frecvent pentru problema jocului de sah, unde numarul de pozitii posibile creste exponential cu numarul de mutari. Acelasi numar de comparatii il presupun si stergerea unei pozitii din lista (care presupune intai gasirea ei) si adaugarea (care presupune ca pozitia de adaugat sa nu existe deja in lista).

Nu vom insista asupra a cum se expandeaza o pozitie si cum se calculeaza efectiv cea mai buna mutare. Noi ne vom interesa de un singur aspect, si anume cautarea unei pozitii in lista. Tehnica cea mai "naturala" este o parcurgere a listei de la cap la coada, comparand pe rand pozitia cautata cu fiecare pozitie din lista. Daca lista are memorate $N$ pozitii, atunci in cazul unei cautari cu succes (pozitia este gasita), numarul mediu de comparatii facute este $N/2$, iar numarul cel mai defavorabil ajunge pana la $N$. In cazul unei cautari fara succes (pozitia nu exista in lista), numarul de comparatii este intotdeauna $N$. De altfel, cazul cautarii fara succes este mult mai frecvent pentru problema jocului de sah, unde numarul de pozitii posibile creste exponential cu numarul de mutari. Acelasi numar de comparatii il presupune si stergerea unei pozitii din lista (care presupune intai gasirea ei) si adaugarea (care presupune ca pozitia de adaugat sa nu existe deja in lista).

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 nici o 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).

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 nici o 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).

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, aidca $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:

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?hash1.JPG!

!tabele-hash-prezentare-detaliata?hash1.jpg!

Iata primul set de proceduri de gestionare a unui Hash.