Este adevărat că timpul de căutare al unui element în unordered_set este constant?

Da, în medie, timpul de căutare al unui element în std::unordered_set este constant — O(1).

Acest lucru se realizează prin utilizarea unui tabel de dispersie. Cheia elementului este hash-ată, iar această valoare este folosită pentru a determina poziția elementului în tabel. Dacă funcția de hash este bună și numărul de coliziuni este minim, accesul la element se face direct.

Totuși, în cel mai rău caz (când există multe coliziuni), timpul de căutare poate deveni liniar — O(n), unde n este numărul de elemente. Acest lucru se întâmplă atunci când toate sau majoritatea elementelor sunt hash-ate în același "bucket" al tabelului de dispersie, iar căutarea se reduce la parcurgerea elementelor din acel bucket.

Factorii care influențează performanța:

• Calitatea funcției de hash.
• Rata de încărcare (load factor) a tabelului de dispersie (raportul dintre numărul de elemente și numărul de buckets). Un factor de încărcare ridicat crește probabilitatea de coliziuni.

#include <unordered_set>
#include <string>
#include <iostream>

int main() {
    std::unordered_set<std::string> mySet;
    mySet.insert("apple");
    mySet.insert("banana");
    mySet.insert("cherry");

    // Căutarea unui element - în medie O(1)
    if (mySet.count("banana")) {
        std::cout << "Găsit: banana" << std::endl;
    } else {
        std::cout << "Banana nu a fost găsit" << std::endl;
    }

    // Exemplu în care pot apărea coliziuni (depinde de funcția de hash și implementare)
    // Influența coliziunilor se manifestă la un număr mare de date
    // și/sau funcție de hash slabă
    return 0;
}