Cum este structurată o tabelă hash în containerul unordered_map?

unordered_map în C++ este implementat ca un tabel hash.

Principiul de funcționare:

1. Hashing: Cheia este transformată într-un număr întreg — cod hash — folosind o funcție hash.
2. Indexare: Codul hash este folosit pentru a determina indexul (găleată sau bucket) într-un array de pointeri sau liste.
3. Stocare: În fiecare găleată se stochează perechi cheie-valoare.

Caracteristici:

• Găleți: Tabelul hash constă dintr-un array de găleți. Numărul de găleți poate fi modificat dinamic (rehashing) atunci când se atinge un anumit factor de încărcare.
• Coliziuni: Chei diferite pot da același cod hash. Acest lucru se numește coliziune. Pentru rezolvarea coliziunilor, unordered_map folosește metoda ** chaining **: elementele cu același hash sunt adăugate într-o listă legată (sau altă structură de date) în găleata corespunzătoare.
• Funcție hash și funcție de comparație: Pentru funcționare corectă sunt necesare două lucruri:
  • O funcție hash bună, care distribuie uniform cheile între găleți, minimizând coliziunile.
  • O funcție de egalitate (==), pentru a distinge cheile cu același cod hash în aceeași găleată.
• Performanță: În medie, operațiile de inserare, ștergere și căutare au complexitate temporară O(1). În cel mai rău caz (de exemplu, multe coliziuni sau o funcție hash prost aleasă), performanța poate scădea la O(n), unde n este numărul de elemente.

Exemplu de structură (simplificat):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Pentru listă legată în găleată
};

struct Bucket {
  Node* head; // Pionier la începutul listei
};

Bucket* buckets; // Array de găleți
size_t num_buckets;

Procesul de adăugare a unui element:

1. Se calculează codul hash al cheii.
2. Se determină indexul găleții: bucket_index = hash(key) % num_buckets.
3. Partea cheie-valoare este adăugată în lista de elemente din acea găleată. Dacă cheia există deja, valoarea se actualizează.

Procesul de căutare a unui element:

1. Se calculează codul hash al cheii.
2. Se determină indexul găleții.
3. Se parcurge lista de elemente din acea găleată, comparând cheile cu cea căutată folosind operatorul ==.

Rehashing-ul are loc atunci când numărul de elemente în raport cu numărul de găleți depășește un prag (factor de încărcare). În timpul rehashing-ului, se creează un nou array de găleți mai mare, iar toate elementele din gălețile vechi sunt re-hash-uite și mutate în cele noi.