}
==

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

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.

* 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.
* Variabilele de tip data se pot converti la intreg prin formula:

$X = A*366 + L*31 + Z$

$X = A * 366 + L * 31 + Z$

unde $A$, $L$ si $Z$ sunt respectiv anul, luna si ziua datei considerate. De fapt, aceasta functie aproximeaza numarul de zile scurse de la inceputul secolului I. Ea nu are pretentii de exactitate (ca dovada, toti anii sunt considerati a fi bisecti si toate lunile a avea 31 de zile), deoarece s-ar consuma timp inutil cu calcule mai sofisticate, fara ca dispersia insasi sa fie imbunatatita cu ceva. Conditia care trebuie neaparat respectata este ca functia de conversie data <tex> \leftrightarrow </tex> intreg sa fie injectiva, adica sa nu se intample ca la doua date $D1$ si $D2$ sa li se ataseze acelasi intreg $X$; daca acest lucru se intampla, pot aparea erori la cautarea in tabela (de exemplu, se poate raporta gasirea datei $D1$ cand de fapt a fost gasita data $D2$). Pentru a respecta injectivitatea, s-au considerat coeficientii $366$ si $31$ in loc de $365$ si $30$. Daca numarul de zile scurse de la 1 ianuarie anul 1 d.H. ar fi fost calculat cu exactitate, functia de conversie ar fi fost si surjectiva, dar, dupa cum am mai spus, acest fapt nu prezinta interes.