Tabele de dispersie

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:

• tablou de liste:

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;
}