Is het waar dat de zoektijd van een element in unordered_set constant is?

Ja, gemiddeld is de zoektijd van een element in std::unordered_set constant — O(1).

Dit wordt bereikt door gebruik te maken van een hashtabel. De sleutel van het element wordt gehasht, en deze hash wordt gebruikt om de positie van het element in de tabel te bepalen. Als de hashfunctie goed is en het aantal collisions minimaal, is de toegang tot het element direct.

Echter, in het slechtste geval (bij veel collisions), kan de zoektijd lineair worden — O(n), waar n het aantal elementen is. Dit gebeurt wanneer alle of de meeste elementen in dezelfde "bucket" van de hashtabel worden gehasht, en de zoekactie zich beperkt tot het doorlopen van de elementen in die bucket.

Factoren die de prestaties beïnvloeden:

• De kwaliteit van de hashfunctie.
• De load factor van de hashtabel (verhouding tussen het aantal elementen en het aantal buckets). Een hoge load factor verhoogt de kans op collisions.

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

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

    // Zoeken naar een element - gemiddeld O(1)
    if (mySet.count("banana")) {
        std::cout << "Gevonden: banana" << std::endl;
    } else {
        std::cout << "Banana niet gevonden" << std::endl;
    }

    // Voorbeeld waar collisions kunnen voorkomen (afhankelijk van de hashfunctie en implementatie)
    // De invloed van collisions manifesteert zich bij grote hoeveelheden data
    // en/of slechte hashfunctie
    return 0;
}