Արդյո՞ք ճիշտ է, որ unordered_set-ում տարրերի որոնման ժամանակը մշտական է։

Այո, միջինում, std::unordered_set-ում տարր որոնելու ժամանակը կայուն է — O(1):

Սա հասնում է հեշային աղյուսակի օգտագործմամբ: Տարրի բանալիքը հեշավորվում է, և այդ հեշը օգտագործվում է տարրի դիրքը որոշելու համար աղյուսակում: Եթե հեշային ֆունկցիան լավ է և բախումների քանակը նվազագույն է, ապա մուտքը տարրին ուղղակի է:

Սակայն, ամենավատ դեպքերում (երբ շատ բախումներ են լինում), որոնման ժամանակը կարող է դառնալ գծային — O(n), որտեղ n տարրերի քանակն է: Դա տեղի է ունենում, երբ բոլոր կամ մեծ մասը տարրերը հեշավորվում են նույն "bucket"-ում, և որոնումը սահմանափակվում է այդ bucket-ի տարրերի անցմամբ:

Աշխատունակության վրա ազդող գործոններ՝

• Հեշային ֆունկցիայի որակը:
• Հաշվարկի գործակիցը (load factor) հեշային աղյուսակի (համեմատությունը տարրերի և bucket-ների միջև): Բարձր գործակիցը մեծացնում է բախումների հավանականությունը:

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

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

    // Տարր որոնում — միջինում O(1)
    if (mySet.count("banana")) {
        std::cout << "գտնվեց: banana" << std::endl;
    } else {
        std::cout << "Banana չի գտնվել" << std::endl;
    }

    // Օրինակ, որտեղ կարող են լինել բախումներ ( dépend de la fonction de hachage et de l'implémentation)
    // Բախումների ազդեցությունը արտահայտվում է մեծ տվյալների քանակի դեպքում
    // և/կամ վատ հեշային ֆունկցիայի դեպքում
    return 0;
}