Hash H;
void InitHash2(Hash H){

    for (int i=0; i<M; H[i++]=NULL);

    for (int i = 0; i < M; H[i++] = NULL);

}
int h2(int K) {

    // Intoarce 0 daca elementul nu exista in hash
    // sau 1 daca el exista
    List *L;

    for (L=H[h2(K)]; L && (L->P != K); L = L->Next);
    return L!=NULL;

    for (L = H[h2(K)]; L && (L->P != K); L = L->Next);
    return L != NULL;

}
void Add2(Hash H, int K) {

* Variabilele de tip string pot fi transformate in numere in baza $256$ prin inlocuirea fiecarui caracter cu codul sau _ASCII_. De exemplu, sirul "abac" poate fi privit ca un numar de 4 cifre in baza $256$, si anume numarul $(97 98 97 99)$. Conversia lui in baza $10$ se face astfel:

$X = ((97 * 256 + 98) * 256 + 97) * 256 + 99 = 1 633 837 411$

$X = ((97 * 256 + 98) * 256 + 97) * 256 + 99 = 1.633.837.411$

Pentru stringuri mai lungi, rezulta numere mai mari. Uneori, ele nici nu mai pot fi reprezentate cu tipurile de date ordinare. Totusi, acest dezavantaj nu este suparator, deoarece majoritatea functiilor de dispersie presupun o impartire cu rest, care, indiferent de marimea numarului de la intrare, produce un numar controlabil.

$X = ((H * 60 + M) * 60 + S) * 100$

daca se tine cont si de sutimile de secunda. De data aceasta, functia este surjectiva (oricarui numar intreg din intervalul 0 - 8.639.999 ii corespunde in mod unic o ora).

daca se tine cont si de sutimile de secunda. De data aceasta, functia este surjectiva (oricarui numar intreg din intervalul $0 - 8.639.999$ ii corespunde in mod unic o ora).

* In majoritatea cazurilor, datele sunt structuri care contin numere si stringuri. O buna metoda de conversie consta in alipirea tuturor acestor date si in convertirea la baza $256$. Caracterele se convertesc prin simpla inlocuire cu codul _ASCII_ corespunzator, iar numerele prin convertirea in baza $2$ si taierea in "bucati" de cate opt biti. Rezulta numere cu multe cifre (prea multe chiar si pentru tipul longint), care sunt supuse unei operatii de impartire cu rest. Functia de conversie trebuie sa fie injectiva. De exemplu, in cazul tablei de sah despre care am amintit mai inainte, ea poate fi transformata intr-un vector cu 64 de cifre in baza 16, cifra 0 semnificand un patrat gol, cifrele 1-6 semnificand piesele albe (pion, cal, nebun, turn, regina, rege), iar cifrele 7-12 semnificand piesele negre. Prin trecerea acestui vector in baza 256, rezulta un numar cu 32 de cifre. La acesta se mai pot adauga alte cifre, respectiv partea la mutare (0 pentru alb, 1 pentru negru), posibilitatea de a efectua rocada mica/mare de catre alb/negru, numarul de mutari scurse de la inceputul partidei si asa mai departe.

* In majoritatea cazurilor, datele sunt structuri care contin numere si stringuri. O buna metoda de conversie consta in alipirea tuturor acestor date si in convertirea la baza $256$. Caracterele se convertesc prin simpla inlocuire cu codul _ASCII_ corespunzator, iar numerele prin convertirea in baza $2$ si taierea in "bucati" de cate opt biti. Rezulta numere cu multe cifre (prea multe chiar si pentru tipul $long long$), care sunt supuse unei operatii de impartire cu rest. Functia de conversie trebuie sa fie injectiva. De exemplu, in cazul tablei de sah despre care am amintit mai inainte, ea poate fi transformata intr-un vector cu $64$ de cifre in baza $16$, cifra $0$ semnificand un patrat gol, cifrele $1-6$ semnificand piesele albe (pion, cal, nebun, turn, regina, rege), iar cifrele $7-12$ semnificand piesele negre. Prin trecerea acestui vector in baza $256$, rezulta un numar cu $32$ de cifre. La acesta se mai pot adauga alte cifre, respectiv partea la mutare ($0$ pentru alb, $1$ pentru negru), posibilitatea de a efectua rocada mica/mare de catre alb/negru, numarul de mutari scurse de la inceputul partidei si asa mai departe.

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

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.

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.

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

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 = 10.000$ 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 $11.000 - 12.000$. Risipa de memorie de circa $1.000 - 2.000$ de intrari in tabela va fi pe deplin compensata de imbunatatirea cautarii.

h2(#metoda-inmultirii). Metoda inmultirii