Aceasta operatie se numeste indexare. Ce-i drept, constructia vectorului $Ind$ nu se poate face intr-un timp mai bun decat $O(N log N)$, dar dupa ce acest lucru se face (o singura data, la inceputul programului), cautarile se pot face foarte repede. Daca pe parcurs se fac adaugari sau stergeri de elemente in/din baza de date, se va pierde catva timp pentru mentinerea indexului, dar in practica timpul acesta este mult mai mic decat timpul care s-ar pierde cu cautarea unor elemente in cazul in care vectorul ar fi neindexat. Nu vom intra in detalii despre indexare, deoarece nu acesta este obiectul capitolului de fata.

In unele situatii nu se poate face nici indexarea structurii de date. Sa consideram cazul unui program care joaca sah. In esenta, modul de functionare al acestui program se reduce la o rutina care primeste o pozitie pe tabla si o variabila care indica daca la mutare este albul sau negrul, rutina intorcand cea mai buna mutare care se poate efectua din acea pozitie. Majoritatea programelor de sah incep sa expandeze respectiva pozitie, examinand tot felul de variante ce pot decurge din ea si alegand-o pe cea mai promitatoare, asa cum fac si jucatorii umani. Pozitiile analizate sunt stocate in memorie sub forma unei liste simplu sau dublu inlantuite. Memorarea nu se poate face sub forma unui vector, deoarece numarul de pozitii analizate este de ordinul sutelor de mii sau chiar al milioanelor, din care cateva zeci de mii sunt retinute in permanenta in memorie.

In unele situatii nu se poate face nici indexarea structurii de date. Sa consideram cazul unui program care joaca sah. In esenta, modul de functionare al acestui program se reduce la o rutina care primeste o pozitie pe tabla si o variabila care indica daca la mutare este albul sau negrul, rutina intorcand cea mai buna mutare care se poate efectua din acea pozitie. Majoritatea programelor de sah incep sa expandeze respectiva pozitie, examinand tot felul de variante ce pot decurge din ea si alegand-o pe cea mai promitatoare, asa cum fac si jucatorii umani. Pozitiile analizate sunt stocate in memorie sub forma unei liste simplu inlantuite. Memorarea nu se poate face sub forma unui vector, deoarece numarul de pozitii analizate este de ordinul sutelor de mii sau chiar al milioanelor, din care cateva zeci de mii sunt retinute in permanenta in memorie.

Sa ne inchipuim acum urmatoarea situatie. Este posibil ca, prin expandarea unei configuratii initiale a tablei sa se ajunga la aceeasi configuratie finala pe doua cai diferite. Spre exemplu, daca albul muta intai calul la _f3_, apoi nebunul la _c4_, pozitia rezultata va fi aceeasi ca si cand s-ar fi mutat intai nebunul si apoi calul (considerand bineinteles ca negrul da in ambele situatii aceeasi replica). Daca configuratia finala a fost deja analizata pentru prima varianta, este inutil sa o mai analizam si pentru cea de-a doua, pentru ca rezultatul (concluzia la care se va ajunge) va fi exact acelasi. Dar cum isi poate da programul seama daca pozitia pe care are de gand s-o analizeze a fost analizata deja sau nu ?

== code(c) |
const int M = 1000;

typedef int Hash[M];

typedef int DataType;

typedef DataType Hash[M];

Hash H;
void InitHash1(Hash H) {

Prin "numar de intrari" in tabela se intelege numarul de elemente ale vectorului $H$; in general, orice tabela hash este un vector. Pentru ca functiile sa fie cat mai generale, am dat tipului de data _int_ un nou nume _DataType_. In principiu, tabelele Hash se aplica oricarui tip de date. In realitate, fenomenul este tocmai cel invers: orice tip de date trebuie "convertit" printr-o metoda sau alta la tipul de date _int_, iar functia de dispersie primeste ca parametru un intreg. Functiile hash prezentate in viitor nu vor mai lucra decat cu variabile de tip intreg. Vom vorbi mai tarziu despre cum se poate face conversia. Acum sa generalizam exemplul de mai sus.

Intr-adevar, cazul anterior este mult prea simplu. Sa ne inchipuim de pilda ca in loc de numere mai mici ca 1000, avem numere de pana la 2.000.000.000. In aceasta situatie posibilitatea de a reprezenta tabela ca un vector caracteristic iese din discutie. Numarul de intrari in tabela este de ordinul miilor, cel mult al zecilor de mii, deci cu mult mai mic decat numarul total de chei (numere) posibile. Ce avem de facut? Am putea incerca sa adaugam un numar $K$ intr-o tabela cu $M$ intrari (numerotate de la 0 la $M-1$) pe pozitia $K mod M$, adica $h(K)=K mod M$. Care va fi insa rezultatul? Functia $h$ isi va pierde proprietatea de injectivitate, deoarece mai multor chei le poate corespunde aceeasi intrare in tabela, cum ar fi cazul numerelor 1234 si 2001234, ambele dand acelasi rest la impartirea prin $M=1000$. Nu putem avea insa speranta de a gasi o functie injectiva, pentru ca atunci numarul de intrari in tabela ar trebui sa fie cel putin egal cu numarul de chei distincte. Vrand-nevrand, trebuie sa rezolvam coliziunile (sau conflictele) care apar, adica situatiile cand mai multe chei distincte sunt repartizate la aceeasi intrare.

Intr-adevar, cazul anterior este mult prea simplu. Sa ne inchipuim de pilda ca in loc de numere mai mici ca 1000, avem numere de pana la 2.000.000.000. In aceasta situatie posibilitatea de a reprezenta tabela ca un vector caracteristic iese din discutie. Numarul de intrari in tabela este de ordinul miilor, cel mult al zecilor de mii, deci cu mult mai mic decat numarul total de chei (numere) posibile. Ce avem de facut? Am putea incerca sa adaugam un numar $K$ intr-o tabela cu $M$ intrari (numerotate de la 0 la $M-1$) pe pozitia $K mod M$, adica $h(K) = K mod M$. Care va fi insa rezultatul? Functia $h$ isi va pierde proprietatea de injectivitate, deoarece mai multor chei le poate corespunde aceeasi intrare in tabela, cum ar fi cazul numerelor 1234 si 2001234, ambele dand acelasi rest la impartirea prin $M=1000$. Nu putem avea insa speranta de a gasi o functie injectiva, pentru ca atunci numarul de intrari in tabela ar trebui sa fie cel putin egal cu numarul de chei distincte. Vrand-nevrand, trebuie sa rezolvam coliziunile (sau conflictele) care apar, adica situatiile cand mai multe chei distincte sunt repartizate la aceeasi intrare.

Vom reveni ulterior la oportunitatea alegerii functiei modul si a numarului de 1000 de intrari in tabela. Deocamdata vom folosi aceste date pentru a explica modul de functionare a tabelei hash pentru functii neinjective. Sa presupunem ca avem doua chei $K1$ si $K2$ care sunt repartizate de functia $h$ la aceeasi intrare $X$, adica $h(K1)=h(K2)=X$. Solutia cea mai comoda este ca $H(X)$ sa nu mai fie un numar, ci o lista liniara simplu sau dublu inlantuita care sa contina toate cheile gasite pana acum si repartizate la aceeasi intrare $X$. Prin urmare vectorul $H$ va fi un vector de liste:

Vom reveni ulterior la oportunitatea alegerii functiei modul si a numarului de 1000 de intrari in tabela. Deocamdata vom folosi aceste date pentru a explica modul de functionare a tabelei hash pentru functii neinjective. Sa presupunem ca avem doua chei $K1$ si $K2$ care sunt repartizate de functia $h$ la aceeasi intrare $X$, adica $h(K1)=h(K2)=X$. Solutia cea mai comoda este ca $H(X)$ sa nu mai fie un numar, ci o lista liniara simplu inlantuita care sa contina toate cheile gasite pana acum si repartizate la aceeasi intrare $X$. Prin urmare vectorul $H$ va fi un vector de liste:

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