Da li je tačno da je vreme pretraživanja elementa u unordered_set konstantno?

Da, u proseku, vreme pretraživanja elementa u std::unordered_set je konstantno — O(1).

Ovo se postiže korišćenjem hash tabele. Ključ elementa se hash-uje, i taj hash se koristi za određivanje pozicije elementa u tabeli. Ako je funkcija hash dobra i broj kolizija minimalan, pristup elementu je direktan.

Međutim, u najgorem slučaju (kada postoji mnogo kolizija), vreme pretraživanja može postati linearno — O(n), gde je n broj elemenata. To se dešava kada su svi ili većina elemenata hash-ovani u isti "bucket" hash tabele, i pretraživanje se svodi na prolazak kroz elemente u tom bucket-u.

Faktori koji utiču na performanse:

• Kvalitet hash funkcije.
• Koeficijent opterećenja (load factor) hash tabele (odnos između broja elemenata i broja bucket-ova). Visok koeficijent opterećenja povećava verovatnoću kolizija.

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

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

    // Pretraga elementa - u proseku O(1)
    if (mySet.count("banana")) {
        std::cout << "Nađeno: banana" << std::endl;
    } else {
        std::cout << "Banana nije pronađena" << std::endl;
    }

    // Primer gde mogu nastati kolizije (zavisi od hash funkcije i implementacije)
    // Uticaj kolizija se manifestuje kod velikog broja podataka
    // i/ili loše hash funkcije
    return 0;
}