Kas on õige, et unordered_set-i elemendi otsimise aeg on konstantne?

Jah, keskmiselt on std::unordered_set-s oleva elemendi otsimise aeg konstantne — O(1).

See saavutatakse kasutades hajutustabelit. Elemendi võti hash-itatakse ning see hash väärtus kasutatakse elemendi positsiooni määramiseks tabelis. Kui hash-funktsioon on hea ja kolisioonide arv on minimaalne, on juurdepääs elemendile otse.

Kuid halvimal juhul (kui on palju kolisioone), võib otsinguaeg muutuda lineaarseks — O(n), kus n on elementide arv. See juhtub, kui kõik või enamik elemente on hash-itud samasse "bucket"-i hajutustabelis ning otsing piirdub selle bucket-i elementide läbivaatamisega.

Tegurid, mis mõjutavad jõudlust:

• Hash-funktsiooni kvaliteet.
• Hajutustabeli laadimistegur (load factor) (suhe elementide arvust bucket-ide arvuni). Kõrge laadimistegur suurendab kolisioonide tõenäosust.

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

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

    // Elementide otsing - keskmiselt O(1)
    if (mySet.count("banana")) {
        std::cout << "Leitud: banana" << std::endl;
    } else {
        std::cout << "Banana ei leitud" << std::endl;
    }

    // Näide, kus võivad tekkida kolisioonid (sõltub hash-funktsioonist ja implementatsioonist)
    // Kolisioonide mõju avaldub suure andmemahtude korral
    // ja/või halva hash-funktsiooni puhul
    return 0;
}