unordered_set'te bir öğenin arama süresinin sabit olduğunu doğru mu?

Evet, ortalama olarak, std::unordered_set içindeki bir öğenin arama süresi sabittir — O(1).

Bu, bir karma tablosu kullanılarak sağlanır. Öğenin anahtarı hashlenir ve bu hash değeri, tablodaki konumunu belirlemek için kullanılır. Eğer hash fonksiyonu iyiyse ve çakışmalar minimalse, öğeye erişim doğrudan gerçekleşir.

Ancak, en kötü durumda (çok sayıda çakışma varsa), arama süresi doğrusal hale gelebilir — O(n), burada n öğe sayısıdır. Bu, tüm veya çoğu öğenin aynı "bucket" içine hashlenmesi durumunda olur ve arama, bu bucketteki öğeleri tek tek gezmeyi gerektirir.

Performansı etkileyen faktörler:

• Hash fonksiyonunun kalitesi.
• Hashtablosunun yük oranı (load factor) (öğe sayısı ile bucket sayısı arasındaki oran). Yüksek yük oranı, çakışma olasılığı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");

    // Öğeyi arama - ortalama O(1)
    if (mySet.count("banana")) {
        std::cout << "Banana bulundu" << std::endl;
    } else {
        std::cout << "Banana bulunamadı" << std::endl;
    }

    // Çakışma olasılığı olan bir örnek (hash fonksiyonuna ve uygulamaya bağlı)
    // Çakışmaların etkisi, büyük veri setlerinde ve/veya kötü hash fonksiyonlarında ortaya çıkar
    return 0;
}