04
Iun
2008

Una dintre adaugarile importante la standardul C++ prin TR1 il reprezinta tabelele hash. Exita patru astfel de tabele, unordered_map si unordered_multimap definite in headerul <unordered_map>, respectic unordered_set si unordered_multiset definite in headerul <unordered_set>. Pe langa acestea, in headerul <functional> exista o clasa template numita hash care reprezinta implementarea pentru functia implicita de hashing pentru aceste containere.

Despre containerele STL

Pana la TR1 in STL existau patru tipuri de containere:

  • containere: un container este un obiect care contine o lista de alte obiecte; un container trebuie sa:
    • contina un constructor default, un constructor de copiere, un destructor (care sa distruga toate obiectele din container), un operator de asignare (care sa copieze toate obiectele dintr-un container in altul).
    • permita accesul la elemente, atat pentru containere constante cat si non-constante (begin() si end())
    • implementeze operatorii de comparatie (==, !=, <, >, <=, and >=)
    • ofere functii de determinare a dimensiunii containerului (size(), max_size() si empty())
    • permita schimbul de elemente intre doua obiecte container(swap())
  • containere reversibile: sunt acele containere care pe langa funtionalitatile unui container simplu permit accesul la elemente in ordine inversa (rbegin() and rend())
  • containere secventa: este un container cu o dimensiune variabila, a carui elemente sunt aranjate intr-o ordine strict liniara, si care permite inserarea si stergere elementelor.
  • containere asociative: este un container cu dimensiune variabila care permite accesul eficient la elemente bazat pe chei (asociate elementelor). Deoebirea fata de containerele secventa e ca nu permite inserarea unui element intr-o anumita pozitie.

In TR1 a fost adaugata a 5-a categorie de containere:

  • containere neordonate: (sau tabele hash) acestea indeplinesc toate cerintele pentru un container, cu exceptia faptului ca nu implementeaza cei sase operatori de comparare. In plus ofera doua type name-uri:
    • key_type, care da tipul cheii,
    • key_equal, care e tipul predicatului folosit pentru compararea a doua chei.

O tabela hash grupeaza elementele in secvente numite "bucket", fiecare astfel de bucket putand avea zero sau mai multe elemente. Inserarea unui element intr-un bucket se face in functie de valoarea de hashing pentru cheia asociata elementului adaugat. In cazul implementarii Microsoft pentru TR1, tabelele hash au in mod implicit 8 bucket-uri, cu factorul de incarcare per bucket, 4. Aceasta inseamna, ca in medie, fiecare bucket poate contine maxim 4 elemente (atentie, aceasta valoare e in medie, si un bucket poate contine 20 elemente, in timp ce toate celelalte bucket-uri sa fie de exemplu goale). Cand un nou element trebuie inserat, si factorul de incarcare este depasit, se adauga un nou bucket si are loc o restructurare completa a tabelei.

Cand se insereaza un element, se calculeaza valoarea de hashing pentru cheia asociata, apoi se aplica functia modulo cu numarul de bucket-uri existente, si valoarea rezultata da indexul bucket-ului in care va fi inserat elementul. Timpul de inserare al unui element este O(1), el nedepinzand de cate elemente exista adaugate in tabel sau bucket.

Atunci cand se cauta un element, se procedeaza in mod asemanator pentru a indentifica bucket-ul. Odata gasit, se aplica functia standard find() pentru a localiza elementul. Aceasta inseamna ca timpul de cautare al unui element este proportional cu numarul de elemente din bucket. Pentru o performanta ridicata, numarul de elemente dintr-un bucket ar trebui pastrat la o valoare rezonabila, si modalitatea de a face acest lucru este adaugarea de noi bucket-uri la tabel.

Containerele neordonate (tabele hash) pot fi parametrizate in mai multe moduri:

  • la compilare, prin specificarea functiei de hashing si de comparare a doua chei
  • la rulare, prin ajustarea factorului maxim permis de incarcare medie a bucketurilor.

Exemplificare evolutie bucket-uri

Voi exemplifica modul in care se adauga elementele in bucket-urile unui unordered_map. De mentionat ca elementul in sine nu are importanta, doar valoarea chei asocitate este importanta pentru acest proces.

  • initial, lista e goala
    buckets: 8
    max load factor: 4
    load factor: 0
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[0]
    
  • adaugam (1, 2); valoarea de hash este 16807, iar pentru aflarea indexului se face modulo 8 (numarul de bucket-uri), si rezulta valoarea 7.
    hash(1) = 16807
    bucket index = 16807 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.125
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[1]     [1,2]
    
  • adaugam (2, 3)
    hash(2) = 33614
    bucket index = 33614 % 8 = 6
    
    buckets: 8
    max load factor: 4
    load factor: 0.25
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[1]     [1,2]
    
  • adaugam (55,100)
    hash(55) = 924385
    bucket index = 924385 % 8 = 1
    
    buckets: 8
    max load factor: 4
    load factor: 0.375
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[1]     [1,2]
    
  • adaugam (9,0);
    hash(9) = 151263
    bucket index = 151263 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.5
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[2]     [9,0] [1,2]
    
  • adaugam (17,0);
    hash(17) = 285719
    bucket index = 285719 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.625
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[3]     [17,0] [9,0] [1,2]
    
  • adaugam (25,0); in acest moment, cel de-al saptelea bucket are deja 4 elemente, dar factorul de incarcare care este o medie a tuturor bucket-urilor este doar 0.75, ceea ce inseamna ca inca se mai pot adauga elemente la acelasi bucket.
    hash(25) = 420175
    bucket index = 420175 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.75
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[4]     [25,0] [17,0] [9,0] [1,2]
    
  • adaugam (33,0); un al cincilea element a fost adaugat la ultimul bucket.
    hash(33) = 554631
    bucket index = 554631 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.875
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[5]     [33,0] [25,0] [17,0] [9,0] [1,2]
    

Pentru a vedea modul in care se adauga noi containere voi folosi un factor de incarcare medie maxima de 0.2. Aceasta inseamna ca la a doua inserare, ar trebuie deja sa se insereze un nou bucket.

  • initial, containerul e gol
    buckets: 8
    max load factor: 0.2
    load factor: 0
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[0]
    
  • adaugam (1,1); se adauga in bucket-ul cu indexul 7
    hash(1) = 16807
    bucket index = 16807 % 8 = 7
    
    buckets: 8
    max load factor: 0.2
    load factor: 0.125
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[1]     [1,1]
    
  • adaugam (2,2); factorul de incarcare ar fi acum 2/8 = 0.25, care este o valoare mai mare decat 0.2; prin urmare, mai intai se adauga un nou bucket, apoi se calculeaza indexul celui in care se va face adaugarea.
    hash(2) = 33614
    bucket index = 33614 % 8 = 6
    
    buckets: 9
    max load factor: 0.2
    load factor: 0.222222
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,2]
    bucket 7[1]     [1,1]
    bucket 8[0]