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

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:

De exemplu, la prima vedere s-ar putea spune ca o buna valoare pentru $M$ este o putere a lui 2, cum ar fi 1024, pentru ca operatia de impartire cu rest se poate face foarte usor in aceasta situatie. Totusi, functia $h(x) = x mod 1024$ are un mare defect: ea nu tine cont decat de ultimii 10 biti ai numarului $x$. Daca datele de intrare sunt numere in mare majoritate pare, ele vor fi repartizate in aceeasi proportie la intrarile cu numar de ordine par, pentru ca functia $h$ pastreaza paritatea. Din aceleasi motive, alegerea unei valori ca 1000 sau 2000 nu este prea inspirata, deoarece tine cont numai de ultimele 3-4 cifre ale reprezentarii zecimale. Multe valori pot da acelasi rest la impartirea prin 1000. De exemplu, daca datele de intrare sunt anii de nastere ai unor persoane dintr-o agenda telefonica, iar functia $h(x)=x mod 1000$, atunci majoritatea cheilor se vor ingramadi (termenul este sugestiv) intre intrarile 920 si 990, restul ramanand nefolosite.

Practic, trebuie ca $M$ sa nu fie un numar rotund in nici o 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 nici o 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.

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