unordered_map — dicționar rapid pe hash

De ce contează?

Imaginează-ți un vestiar cu mii de dulapuri. Dacă fiecare elev are un dulap cu numărul lui scris pe cheie, nu cauți prin tot rândul: te duci direct la dulapul care îți aparține. Asta face un tabel hash — transformă cheia într-o „adresă” și sare direct acolo, fără să răsfoiască restul.

Ce este unordered_map și de ce există?

Un unordered_map este un dicționar: leagă o cheie de o valoare și îți răspunde rapid la întrebarea „ce valoare are cheia asta?”. Spre deosebire de map, nu ține cheile sortate — de aici și numele.

Secretul vitezei e tabelul hash. O funcție de hash transformă fiecare cheie într-un număr, iar acel număr indică direct „cutia” (bucket) în care stă perechea. Nu mai compari cheia cu toate celelalte: calculezi hash-ul și mergi țintit. De aceea inserarea, căutarea și accesul cu [] sunt în medie O(1), indiferent câte elemente ai.

Compromisul: pierzi ordinea. Dacă iterezi, cheile ies într-o ordine imprevizibilă, dictată de hash, nu de valoarea lor.

Exemplu pas cu pas: frecvența cuvintelor

Vrei să numeri de câte ori apare fiecare cuvânt în textul mar pere mar gut mar pere. Pornești cu dicționarul gol și, pentru fiecare cuvânt, faci frec[cuvant]++:

citești mar → cheia nu există, [] o creează cu 0, apoi ++ → mar: 1
citești pere → creată → pere: 1
citești mar → există deja → mar: 2
citești gut → creată → gut: 1
citești mar → mar: 3
citești pere → pere: 2

frec	3	2	1
cheie	mar	pere	gut

Stare finală a dicționarului. Atenție: pozițiile reale în tabelul hash NU respectă ordinea de mai sus.

Fiecare frec[cuvant]++ a fost în medie O(1), deci tot procesul e O(n) pentru n cuvinte — mult mai rapid decât să cauți de fiecare dată prin listă.

Implementare C++

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> frec;

    string cuvinte[] = {"mar", "pere", "mar", "gut", "mar", "pere"};
    for (string c : cuvinte) {
        frec[c]++;              // [] creeaza cheia cu 0 daca lipseste, apoi ++
    }

    // acces direct la o cheie
    cout << frec["mar"] << "\n";   // 3

    // cautare sigura, fara sa creezi intrari noi
    if (frec.find("kiwi") != frec.end()) {
        cout << "kiwi exista\n";
    } else {
        cout << "kiwi lipseste\n"; // kiwi lipseste
    }

    // iterare (ordine NEPREVIZIBILA)
    for (auto& [cheie, val] : frec) {
        cout << cheie << " -> " << val << "\n";
    }
    // posibil: gut -> 1 / mar -> 3 / pere -> 2 (sau orice alta ordine)

    cout << frec.size() << "\n";   // 3 (numar de chei distincte)
    return 0;
}

Reține cele patru operații-cheie: m[k] (acces/creare), m.find(k) (căutare fără efecte secundare), m.count(k) (0 sau 1), m.size() (câte chei ai).

Complexitate

Operație	Mediu	Cel mai rău
insert / `[]` / `find` / `count`	O(1)	O(n)
iterare prin toate cheile	O(n)	O(n)
ordine de iterare	neordonată	neordonată

Cazul O(n) apare când multe chei se ciocnesc în același bucket (coliziuni) și acel bucket devine practic o listă pe care trebuie să o parcurgi.

Observația-cheie

Regula simplă de alegere: vrei doar viteză și nu-ți pasă de ordine → unordered_map. Ai nevoie de chei sortate sau de lower_bound → map (O(log n), dar ordonat).

Greșeli frecvente

Greșeli frecvente:

Te bazezi pe ordine: iterarea printr-un unordered_map NU dă cheile sortate, nici în ordinea inserării. Dacă rezultatul trebuie sortat, folosește map sau copiază într-un vector și sortează.
m[cheie] creează intrarea: simpla citire if (m[k] == ...) adaugă cheia k cu valoarea 0 dacă lipsea, mărind size(). Pentru verificare folosește find sau count.
Ignori cazul O(n): în medie e O(1), dar coliziunile îl pot face O(n). La concurs cu chei „ostile” (anti-hash) timpul poate exploda — rar la clasa a 10-a, dar bun de știut; soluția e un hash personalizat.
Alegi unordered_map când ai nevoie de sortare: dacă vrei minimul, maximul sau interval de chei, map îți dă asta direct prin ordonare și lower_bound.

Vizualizare

Urmărește cum o cheie e transformată în hash și aterizează într-un bucket:

Indiciu

Observă că două chei diferite pot cădea în același bucket — exact o coliziune. Folosește ← / → pentru a vedea inserarea și căutarea pas cu pas.

Recapitulare

unordered_map = dicționar cheie→valoare pe tabel hash: insert/find/[] în medie O(1), dar neordonat.
m[cheie] creează intrarea dacă lipsește; pentru verificare pură folosește find sau count.
Alegi unordered_map pentru viteză fără ordine; alegi map când ai nevoie de chei sortate sau lower_bound.