unordered_set-də elementin axtarış vaxtı sabitdir?

Bəli, orta hesabla, std::unordered_set içində elementin axtarış vaxtı sabitdir — O(1).

Bu, hash cədvəlindən istifadə etməklə əldə edilir. Elementin açarı hash-lənir və bu hash dəyəri elementin cədvəldəki mövqeyini müəyyən etmək üçün istifadə olunur. Əgər hash funksiyası yaxşıdır və kolliziyalar minimaldirsə, elementə birbaşa çıxış mümkündür.

Lakin, ən pis halda (çox kolliziya olarsa), axtarış vaxtı lineyar ola bilər — O(n), burada n elementlərin sayıdır. Bu, bütün və ya çoxlu elementlərin eyni "bucket"-a hash-ləndiyi zaman baş verir və axtarış bu bucket-dəki elementləri yoxlamağa məcbur olur.

Performansa təsir edən amillər:

• Hash funksiyasının keyfiyyəti.
• Hash cədvəlinin yüklənmə faktoru (load factor) (elementlərin sayı ilə bucketların sayı arasındakı nisbət). Yüksək yüklənmə faktoru kolliziya ehtimalını artırır.

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

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

    // Elementin axtarışı - orta hesabla O(1)
    if (mySet.count("banana")) {
        std::cout << "Tapıldı: banana" << std::endl;
    } else {
        std::cout << "Banana tapılmadı" << std::endl;
    }

    // Kolliziya ola biləcək nümunə (hash funksiyasına və implementasiyaya bağlıdır)
    // Kolliziya təsiri böyük məlumat kütlələrində və ya zəif hash funksiyasında özünü göstərir
    return 0;
}