Je pravda, že čas vyhľadávania prvku v unordered_set je konštantný?

Áno, priemerný čas vyhľadávania prvku v std::unordered_set je konštantný — O(1).

Toto sa dosahuje použitím hashovacej tabuľky. Kľúč prvku je hashovaný a tento hash sa používa na určenie pozície prvku v tabuľke. Ak je hashovacia funkcia dobrá a počet kolízií je minimálny, prístup k prvku je priamy.

Avšak, v najhoršom prípade (keď je veľa kolízií), môže sa čas vyhľadávania stať lineárnym — O(n), kde n je počet prvkov. To sa stáva, keď všetky alebo väčšina prvkov je hashovaná do toho istého "bucketu" hashovacej tabuľky, a vyhľadávanie sa zredukuje na prechádzanie prvkov v tomto bucketu.

Faktory, ktoré ovplyvňujú výkon:

• Kvalita hashovacej funkcie.
• Koeficient zaťaženia (load factor) hashovacej tabuľky (pomery medzi počtom prvkov a počtom bucketov). Vysoký koeficient zvyšuje pravdepodobnosť kolízií.

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

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

    // Vyhľadávanie prvku - priemerne O(1)
    if (mySet.count("banana")) {
        std::cout << "Nájdené: banana" << std::endl;
    } else {
        std::cout << "Banana nenájdená" << std::endl;
    }

    // Príklad, kde môžu nastať kolízie (závisí od hash funkcie a implementácie)
    // Vplyv kolízií sa prejavuje pri veľkom množstve dát
    // a/ alebo zlej hash funkcii
    return 0;
}