Czy czas wyszukiwania elementu w unordered_set jest stały?

Tak, średnio czas wyszukiwania elementu w std::unordered_set jest stały — O(1).

Osiąga się to dzięki użyciu tablicy haszującej. Klucz elementu jest haszowany, a ten hash jest używany do określenia pozycji elementu w tablicy. Jeśli funkcja hash jest dobra i liczba kolizji jest minimalna, dostęp do elementu jest bezpośredni.

Jednak w najgorszym przypadku (przy dużej liczbie kolizji), czas wyszukiwania może stać się liniowy — O(n), gdzie n to liczba elementów. Dzieje się tak, gdy wszystkie lub większość elementów jest haszowanych do tego samego "bucket" w tablicy haszującej, a wyszukiwanie sprowadza się do przeszukiwania elementów w tym bucket.

Czynniki wpływające na wydajność:

• Jakość funkcji hashującej.
• Współczynnik obciążenia (load factor) tablicy haszującej (stosunek liczby elementów do liczby bucketów). Wysoki współczynnik obciążenia zwiększa prawdopodobieństwo kolizji.

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

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

    // Wyszukiwanie elementu - średnio O(1)
    if (mySet.count("banana")) {
        std::cout << "Znaleziono banana" << std::endl;
    } else {
        std::cout << "Banana nie znaleziona" << std::endl;
    }

    // Przykład, gdzie mogą wystąpić kolizje (zależy od funkcji hash i implementacji)
    // Wpływ kolizji ujawnia się przy dużej ilości danych
    // i/lub złej funkcji hashującej
    return 0;
}