Există, însă. aplicații informatice în care operațiile de căutare a unui element după valoare și de înserare a unui element nou sunt foarte frecvente. Pentru astfel de situații, era firesc să se caute o structură de date la care operațiile menționate sa aibă complexitatea O(1), adică să nu depindă semnificativ de numărul de elemente din colecție. O astfel de structură este tabela de dispersie.
Fie un tablou de obiecte unidimensional de lungime n,
în care numai o parte din elemente sunt ocupate, celelalte conținând
referința null. Fie X mulțimea din care se aleg
elementele care vor fi puse în tablou. Vom considera că numărul de
elemente din mulțimea X (card(X)) este mult mai mare
decât lungimea n a tabloului, dar numărul de elemente
care se vor pune efectiv in tablou este mai mic decat n.
Considerăm că, pentru elementele multimii X, se poate calcula o funcție
de dispersie h(x, n), care are următoarele
proprietăți:
- pentru orice element x, valoarea funcției de
dispersie h(x, n) este un număr întreg cuprins în
intervalul [0, n-1];
- dacă două elemente x1 și x2 sunt
identice, atunci și valorile funcției de dispersie aplicată acestor
elemente sunt egale, deci h(x1, n)==h(x2,
n);
- întrucât funcția de dispersie este astfel aleasă, încât
frecvențele valorii ei să fie uniform distribuite pe intervalul [0,
n-1] (adică, în mulțimea X numărul de obiecte cu aceeași
valoare a funcției h(x, n) să fie aproximativ același
pentru fiecare din valorile cuprinse în intervalul [0, n-1]).
Foarte frecvent, funcția de dispersie se calculează pentru
șiruri de caractere. Pentru șirul x = x[0]x[1]x[2]...x[m-1] funcția de dispersie poate fi calculată cu formula h(x, n) = (x[0] + x[1].B1 + x[2].B2 + ... + x[m-1].Bm-1) mod n unde m - lungimea șirului; n - capacitatea tanelei de dispersie; B - baza sistemului de condificare a caracterelor (256 pentru codul ASCII pe 8 biți); mod - operatorul modulo (restul împărțirii întregi). De regulă, se adoptă drept capacitate n a tabelei de dispersie un număr prim, pentru a nu se produce interferențe intre înmulțirea cu B și împărțirea la n. |
În Java, după cum se știe, în clasa Object este definită funcția int
hashCode(), care întoarce un "cod de dispersie" al
obiectului respectiv sub forma de număr întreg, fiind recomandabil să
se redefinească această functiț pentru fiecare clasă. În acest caz,
pentru un n dat, funcția de dispersie a
obiectului ob poate fi definită sub forma
h(ob)=ob.hashCode()% n
(amintim ca operatorul % calculează restul împărțirii întregi, deci
funcția modulo).
Tabela de dispersie este un tablou, în care elementele se plaseaza în conformitate cu valoarea funcției de dispersie pentru elementul respectiv. Tabela nu este niciodata plină. Raportul dintre numărul de elemente existente efectiv în tabela de dispersie și lungimea acesteia se numește factor de umplere.
- Figura 1 -
Tabela de dispersie poate fi reprezentată prin schema din figura 1. Elementele tabelei sunt obiectele A, B, C, D, E, F. Tabloul conține numai referințe la aceste elemente, iar celulele libere conțin referința null. Denumirea de tabelă de dispersie provine tocmai de la faptul că, atât referințele la elemente, cât și celulele libere sunt dispersate (împrăștiate în mod uniform) pe întreaga lungime a tabelei.
Valoarea funcției de dispersie i = h(x) reprezintă
indicele i la care elementul x poate
fi pus în tabelă. Este posibil însă ca poziția respectivă din
tablou sa fie deja ocupată de un alt element cu aceeași valoare a
funcției de dispersie. În acest caz, are loc o coliziune.
Pentru a rezolva coliziunea, se caută în tabelă prima poziție liberă
de indice j > i și se pune acolo elementul x.
Considerăm o clasă de tabele de dispersie, în care există
câmpul Object tab[] care servește ca tablou de referințe la elemente. Metoda pentru punerea unui element x în tabloul tab este următoarea: void puneElement(Object x) { |
Căutarea unui element în tabela de dispersie se face în mod
asemănător cu punerea acestuia: se calculează funcția de dispersie a
elementului căutat și se determină astfel indicele din tablou de la
care începe căutarea elementului. Căutarea se termină în una din
urmatoarele situații:
- s-a găsit elementul căutat, și se întoarce indicele i al acestuia;
- dacă s-a ajuns la o poziție liberă (null), se întoarce -1.
Pentru căutarea elementului în tabelă se poate folosi
următoarea funcție:
int caută(Object x){ |
Observație: atât la punerea elementelor în tabelă, cât și la căutarea acestora, tabela este considerata circulară: dacă s-a ajuns la capătul tabelei fără a gasi un element nul, se continuă căutarea de la începutul tabelei (de la poziția de indice 0). Cel puțin un element nul trebuie să existe, deoarece se are grijă ca factorul de umplere să fie totdeauna subunitar. Metodele de căutare în tabelă date mai sus trebuie, în acest caz, modificate astfel încât să realizeze căutarea circulară.
Remarcăm că, dacă factorul de umplere nu este prea mare, deci există
suficiente celule libere dispersate pe lungimea tabelei, numărul de
comparații făcute pentru a pune un element în tabelă sau a căuta un
element existent este relativ mic și nu depinde de lungimea tabelei, ci
doar de factorul de umplere. Într-adevar, numărul de pași de căutare
este cel mult egal cu diferența dintre valoarea funcției de dispersie a
elementului căutat h(x, n) și indicele primei celule
libere a tabelei situată sub locul de unde începe căutarea. Putem deci
considera că, atât la punerea de elemente în tabelă, cât și la căutarea
acestora, complexitatea este O(1). Practica arată că
aceasta afirmație este corectă pentru valori ale factorului de umplere
care nu depășesc 0.75.