Să considerăm următoarea problemă:
Se dă o mulțime cu n numere naturale și m întrebări de forma: valoarea X face parte sau nu din mulțime .
Practic avem nevoie de o structură de date care să permită operațiile Caută, Șterge, Inserează cu o complexitate cât mai mică, de preferință O(1)!
Dacă valorile din mulțime sunt relativ mici (să spunem că până la 1000000), o variantă simplă de rezolvare este să folosim un vector caracteristic. Dacă însă valorile date sunt mari, vectorul caracteristic nu mai este o soluție. O modalitatea de rezolvare este folosirea unei tabele de dispersie – tabelă hash.
Tabela hash este o structură de date prin care valorile cu care lucrăm sunt transformate în valori numerice dintr-un interval numeric stabilit printr-un algoritm unidirecțional, numit funcție de dispersie, și adăugate într-o structură de date care de regulă are dimensiuni mici și care este identificată prin valoarea funcției de dispersie. Astfel, mulțimea valorilor este partiționată astfel încât toate valorile dintr-o submulțime a partiției dau aceiași valoare prin funcția de dispersie.
De exemplu, sa consideram valorile 398 572 944 590 514 981 69 739 499 741 și o funcție de dispersie f(x) = x % 10. În acest caz, mulțimea valorilor se va partiționa în 10 submulțimi, cu următoarele valori:
0 -> {590}
1 -> {981, 741}
2 -> {572}
3 -> {}
4 -> {944, 514}
5 -> {}
6 -> {}
7 -> {}
8 -> {398}
9 -> {69, 739, 499}
Pentru funcția de dispersie f(x) = x % 9 obținem următoarea distribuție a valorilor în tabelă:
0 -> {981}
1 -> {514, 739}
2 -> {398}
3 -> {741}
4 -> {499}
5 -> {572, 590}
6 -> {69}
7 -> {}
8 -> {944}
Constatăm că în ambele situații avem coliziuni (valori din mulțimea dată pentru care valoarea funcției de dispersie este comună). Pentru stocarea valorilor în tabela de dispersia avem nevoie de o structură de date convenabilă. Aceasta poate fi:
struct nod{
int info;
nod * next;
};
const int N = 10;
nod * H[N];
- vector de vectori STL – această variantă este mai convenabilă, fiind mai ușor de implementat:
int N = 10;
vector<vector<int>> V(n);
Următorul program plasează într-o tabelă hash implementată prin vectori STL valorile din exemplul de mai sus:
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int main(){
string T = "398 572 944 590 514 981 69 739 499 741";
istringstream sin(T);
int n = 10;
vector<vector<int>> H(n);
int x;
while(sin >> x)
H[x % n].push_back(x);
for(int i = 0 ; i < n ; i ++)
{
cout << i << " -> {";
int cnt = 0;
for(auto x : H[i])
{
if(cnt == 0)
cout << x;
else
cout << ", " << x;
cnt ++;
}
cout << "}\n";
}
return 0;
}
Candale Silviu (silviu)