Exista insa aplicatii informatice in care operatiile de cautare a unui element dupa valoare si de inserare a unui nou sunt foarte frecvente. Pentru astfel de situatii, era firesc sa se caute o structura de date la care operatiile mentionate sa aiba complexitatea O(1), adica sa nu depinda semnificativ de numarul de elemente. O astfel de structura este tabela de dispersie.
Fie un tablou de obiecte unidimensional de lungime n,
in care numai o parte din elemente sunt ocupate, celelalte continand referinta
null.
Fie X multimea din care se aleg elementele care vor fi puse in tablou.
Numarul de elemente din multimea X este mult mai mare decat lungimea
n a tabloului, dar numarul de elemente care se vor pune efectiv
in tablou este mai mic decat n. Consideram ca pentru elementele
multimii X se poate calcula o functie de dispersie, care are urmatoarele
proprietati:
- pentru orice element x, valoarea
functiei de dispersie h(x, n) este un numar intreg cuprins
in intervalul [0, n-1];
- daca doua elemente x1 si x2
sunt identice, atunci si valorile functiilor de dispersie aplicate acestor
elemente sunt egale, deci h(x1, n)==h(x2,
n);
- intrucat functia de dispersie este astfel aleasa,
incat frecventa valorii ei sa fie uniform distribuita pe intervalul [0,
n-1] (adica, in multimea X numarul de obiecte cu aceeasi valoare
a functiei h(x, n) sa fie aproximativ acelasi pentru fiecare
din valorile cuprinse in intervalul [0, n-1]).
Foarte frecvent, functia de dispersie se calculeaza pentru siruri de
caractere. Pentru sirul
x = x[0]x[1]x[2]...x[m-1] functia de dispersie poate fi calculata cu formula h(x, n) = (x[0] + x[1].B1 + x[2].B2 + ... + x[m-1].Bm-1) mod n unde m - lungimea sirului; n - numarul de elemente din tablou; B - baza sistemului de condificare a caracterelor (256 pentru codul ASCII pe 8 biti); mod - operatorul modulo (restul impartirii intregi). De regula, se adopta numarul de elemente din tablou n numar prim, pentru a nu se produce interferente intre inmultirea cu B si impartirea la n. |
In Java, dupa cum se stie, in clasa Object este definita functia int
hashCode(), care intoarce un "cod de dispersie" al obiectului
respectiv sub forma de numar intreg, fiind recomandabil sa se redefineasca
aceasta functie pentru fiecare clasa. In acest caz, pentru un n
dat, functia de dispersie a obiectului ob poate fi definita
sub forma
h(ob)=ob.hashCode()% n
(amintim ca operatorul % calculeaza restul impartirii intregi, deci
functia modulo).
Tabela de dispersie este un tablou, in care elementele se plaseaza in conformitate cu valoarea functiei de dispersie pentru elementul respectiv. Tabela nu este niciodata plina. Raportul dintre numarul de elemente existente efectiv in tabela de dispersie si lungimea acesteia se numeste factor de umplere.
- Figura 1 -
Tabela de dispersie poate fi reprezentata prin schema din figura 1. Elementele tabelei sunt obiectele A, B, C, D, E, F. Tabloul contine numai referinte catre aceste elemente, iar celulele libere contin referinta null. Denumirea de tabela de dispersie provine tocmai de la faptul ca, atat referintele la elemente, cat si celulele libere sunt dispersate (imprastiate) in mod pe intreaga lungime a tabelei.
Valoarea functiei de dispersie i = h(x) reprezinta indicele
i
la care elementul x poate fi pus in tabela.
Este posibil insa ca pozitia respectiva din tablou sa fie deja ocupata
de un alt element cu aceeasi valoare a functiei de dispersie. In acest
caz, are loc o coliziune. Pentru a rezolva coliziunea, se
cauta in tabela o pozitie libera de indice j > i
si
se pune acolo elementul x.
Consideram o clasa de tabele de dispersie, in care exista campul
Object tab[] care serveste ca tablou de referinte la elemente. Metoda pentru punerea unui element x in tabloul tab este urmatorul: void puneElement(Object x) {
|
Cautarea unui element in tabela de dispersie se face in mod asemanator
cu punerea acestuia: se calculeaza functia de dispersie a elementului cautat
si se determina astfel indicele din tablou de la care incepe cautarea elementului.
Cautarea se termina in una din urmatoarele conditii:
- s-a gasit elementul cautat, se intoarce indicele i pe
care acesta exista;
- daca s-a ajuns la o pozitie libera (null) sau
la capatul tabloului se intoarce -1.
Pentru cautarea elementului in tabela se poate folosi urmatoarea functie:
int cauta(Object x){
|
Remarcam ca, daca factorul de umplere nu este prea mare, deci exista
suficiente celule libere dispersate pe lungimea tabelei, numarul de comparatii
facute pentru a pune un element in tabela sau a cauta un element existent
este relativ mic si nu depinde de lungimea tabelei, ci doar de factorul
de umplere. Intr-adevar, numarul de pasi de cautare este cel mult egal
cu diferenta dintre valoarea functiei de dispersie a elementului cautat
si indicele primei celule libere a tabelei situata sub locul de unde incepe
cautarea. Putem deci considera ca, atat la punerea de elemente in tabela,
cat si la cautarea acestora, complexitatea este O(1). Practica
arata ca aceasta afirmatie este corecta pentru valori ale factorului de
umplere care nu depasesc 0.75.