Tabele de dispersie

Conceptul de tabelă de dispersie

Din analiza structurilor de date studiate anterior s-a constatat că:
    - în cazul tablourilor, complexitatea accesului la un element după indice este O(1), însă complexitatea căutării unui element în tablou după valoare este O(n) în cazul tablourilor nesortate și O(log n) în cazul căutării binare în tablourile sortate; în plus, în cazul tablourilor, nu este posibilă adăugarea sau eliminarea de elemente, ci doar înlocuirea unor elemente prin altele;
    - în cazul listelor implementate ca tablou, complexitățile operațiilor de acces după indice și de căutare sunt aceleași ca în cazul tablourilor; complexitatea înserării în listă sau eliminării unui element din interior, complexitatea exte O(n);
    - în cazul listelor înlănțuite, complexitatea adaugării sau eliminării elementelor din capul și coada listei este O(1); în schimb, căutarea unui element după indice sau după valoare, înserarea și eliminarea unui element situat în interior, au complexitatea O(n).

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) { 
    boolean gasitLoc=false;
    int i= h(x, tab.length); // h(x, n) este funcția de dispersie
    while(i < tab.length-1 &&  !gasitLoc) {
      if (tab[i].equals(x)) gasitLoc=true; // elementul deja există
      else if (tab[i] == null) { // s-a găsit o pozitie liberă
        tab[i]= x; // Se pune x pe poziția liberă gasită
        gasitLoc=true;
      }
      i++;
    }
  }
 

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){
     int i=h(x, tab.length);
     while(i<tab.length && tab[i] != null) 
       if(x.equals(tab[i])) return i;
     return -1;
   }

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați