Ar teisinga, kad elementų paieškos laikas unordered_set yra pastovus?

Taip, vidutiniškai, elementų paieškos laikas std::unordered_set yra pastovus — O(1).

Tai pasiekiama naudojant maišos lentelę. Elemento raktas yra maišos funkcija, ir ši reikšmė naudojama nustatyti elemento poziciją lentelėje. Jei maišos funkcija yra gera ir kolizijų skaičius yra minimalus, prieiga prie elemento yra tiesioginė.

Tačiau blogiausiu atveju (kai yra daug kolizijų), paieškos laikas gali tapti linijinis — O(n), kur n yra elementų skaičius. Tai įvyksta, kai visi arba dauguma elementų yra maišomi į tą patį "bucket" maišos lentelėje, ir paieška apsiriboja elementų peržiūra šiame bucket'e.

Veiksniai, turintys įtakos našumui:

• Maišos funkcijos kokybė.
• Užpildymo koeficientas (load factor) maišos lentelėje (elementų skaičius santykyje su bucket'ų skaičiumi). Aukštas koeficientas didina kolizijų tikimybę.

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

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

    // Elemento paieška - vidutiniškai O(1)
    if (mySet.count("banana")) {
        std::cout << "Rasta: banana" << std::endl;
    } else {
        std::cout << "Banana nerasta" << std::endl;
    }

    // Pavyzdys, kai gali būti kolizijų (priklauso nuo hash funkcijos ir įgyvendinimo)
    // Kolizijų įtaka pasireiškia dideliame duomenų kiekyje
    // ir/arba blogoje hash funkcijoje
    return 0;
}