Je pravda, že doba hledání prvku v unordered_set je konstantní?

Ano, průměrná doba hledání prvku v std::unordered_set je konstantní — O(1).

Toho je dosaženo použitím hashovací tabulky. Klíč prvku je hashován a tento hash se používá k určení pozice prvku v tabulce. Pokud je hashovací funkce dobrá a počet kolizí minimální, přístup k prvku je přímý.

Nicméně, v nejhorším případě (když je mnoho kolizí), může se doba hledání stát lineární — O(n), kde n je počet prvků. K tomu dochází, když jsou všechny nebo většina prvků hashovány do stejného "bucketu" hashovací tabulky, a hledání se zkracuje na prohledávání prvků v tomto bucketu.

Faktory ovlivňující výkon:

• Kvalita hashovací funkce.
• Koeficient zatížení (load factor) hashovací tabulky (poměr počtu prvků k počtu bucketů). Vyšší koeficient zátěže zvyšuje pravděpodobnost kolizí.

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

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

    // Vyhledávání prvku - průměrně O(1)
    if (mySet.count("banana")) {
        std::cout << "Nalezeno: banana" << std::endl;
    } else {
        std::cout << "Banana nenalezena" << std::endl;
    }

    // Příklad, kde mohou nastat kolize (závisí na hashovací funkci a implementaci)
    // Vliv kolizí se projevuje při velkém množství dat
    // a/nebo špatné hashovací funkci
    return 0;
}