Igaz, hogy az unordered_set-ben lévő elem keresési ideje konstans?

Igen, átlagosan a std::unordered_set-ben való elemkeresés időtartama állandó — O(1).

Ez a hash-tábla használatával érhető el. Az elem kulcsa hash-elve lesz, és ezt az értéket használják az elem pozíciójának meghatározására a táblában. Ha a hash-függvény jó és a kollíziók minimálisak, az elemhez való hozzáférés közvetlen.

Azonban a legrosszabb esetben (amikor sok kollízió van), a keresési idő lineárissá válhat — O(n), ahol n az elemek száma. Ez akkor fordul elő, amikor az összes vagy a legtöbb elem ugyanabba a "bucket"-be hash-elt, és a keresés az ebben a bucketben lévő elemek áttekintésére korlátozódik.

A teljesítményt befolyásoló tényezők:

• A hash-függvény minősége.
• A hash-tábla töltési tényezője (load factor) (az elemek száma és a bucketek száma közötti arány). Magas töltési tényező növeli a kollíziók valószínűségét.

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

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

    // Elem keresése - átlagosan O(1)
    if (mySet.count("banana")) {
        std::cout << "Megtalálva: banana" << std::endl;
    } else {
        std::cout << "Banana nem található" << std::endl;
    }

    // Példa, ahol kollíziók fordulhatnak elő (a hash-függvénytől és a megvalósítástól függ)
    // A kollíziók hatása nagy adatmennyiség esetén és/vagy rossz hash-függvény esetén jelentkezik
    return 0;
}