Ist es richtig, dass die Suchzeit eines Elements in unordered_set konstant ist?

Ja, im Durchschnitt ist die Suchzeit eines Elements in std::unordered_set konstant — O(1).

Dies wird durch die Verwendung einer Hashtabelle erreicht. Der Schlüssel des Elements wird gehasht, und dieser Hash-Wert wird verwendet, um die Position des Elements in der Tabelle zu bestimmen. Wenn die Hash-Funktion gut ist und die Kollisionen minimal sind, erfolgt der Zugriff auf das Element direkt.

Im schlimmsten Fall (bei vielen Kollisionen) kann die Suchzeit linear werden — O(n), wobei n die Anzahl der Elemente ist. Dies passiert, wenn alle oder die meisten Elemente in denselben "Bucket" der Hashtabelle gehasht werden, und die Suche sich auf das Durchlaufen der Elemente in diesem Bucket beschränkt.

Faktoren, die die Leistung beeinflussen:

• Die Qualität der Hash-Funktion.
• Der Ladefaktor (load factor) der Hashtabelle (Verhältnis zwischen der Anzahl der Elemente und der Anzahl der Buckets). Ein hoher Ladefaktor erhöht die Wahrscheinlichkeit von Kollisionen.

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

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

    // Suche nach einem Element - im Durchschnitt O(1)
    if (mySet.count("banana")) {
        std::cout << "Gefunden: banana" << std::endl;
    } else {
        std::cout << "Banana nicht gefunden" << std::endl;
    }

    // Beispiel, bei dem Kollisionen auftreten können (abhängig von der Hash-Funktion und Implementierung)
    // Der Einfluss von Kollisionen zeigt sich bei großen Datenmengen
    // und/oder schlechter Hash-Funktion
    return 0;
}