Tabele de dispersie

Conceptul de tabela de dispersie

Din analiza structurilor de date studiate anterior s-a constatat ca:
    - in cazul tablourilor complexitatea accesului la un element dupa indice este O(1), insa complexitatea cautarii unui element in tablou dupa valoare este O(n) in cazul tablourilor nesortate si O(log n) in cazul celor sortate; in plus, adaugarea sau eliminarea de elemente nu este posibila;
    - in cazul listelor implementate ca tablou, complexitatile operatiilor de acces dupa indice si de cautare sunt aceleasi ca in cazul tablourilor; complexitatea inserarii in lista sau eliminarii unui element din interior, complexitatea exte O(n);
    - in cazul listelor inlantuite, complexitatea adaugarii sau eliminarii elementelor din capul si coada listei este O(1); in schimb, cautarea unui element dupa indice sau dupa valoare, inserarea si eliminarea unui element situat in interior, au complexitatea O(n).

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) { 
    boolean gasitLoc=false;
    int i= h(x, tab.length); // h(x, n) este functia de dispersie
    while(i < tab.length-1 &&  !gasitLoc) {
      if (tab[i].equals(x)) gasitLoc=true; // elementul deja exista
      else if (tab[i] == null) { // s-a gasit o pozitie libera
        tab[i]= x; // Se pune x pe pozitia libera gasita
        gasitLoc=true;
      }
      i++;
    }
  }
 

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

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati