Est-il vrai que le temps de recherche d'un élément dans unordered_set est constant?

Oui, en moyenne, le temps de recherche d'un élément dans std::unordered_set est constant — O(1).

Cela est réalisé grâce à l'utilisation d'une table de hachage. La clé de l'élément est hachée, et cette valeur est utilisée pour déterminer la position de l'élément dans la table. Si la fonction de hachage est bonne et que le nombre de collisions est minimal, l'accès à l'élément est direct.

Cependant, dans le pire des cas (lorsqu'il y a beaucoup de collisions), le temps de recherche peut devenir linéaire — O(n), où n est le nombre d'éléments. Cela se produit lorsque tous ou la majorité des éléments sont hachés dans le même "bucket" de la table de hachage, et la recherche revient à parcourir les éléments dans ce bucket.

Facteurs influençant la performance :

• La qualité de la fonction de hachage.
• Le facteur de charge (load factor) de la table de hachage (rapport entre le nombre d'éléments et le nombre de buckets). Un facteur de charge élevé augmente la probabilité de 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");

    // Recherche d'un élément - en moyenne O(1)
    if (mySet.count("banana")) {
        std::cout << "Trouvé banana" << std::endl;
    } else {
        std::cout << "Banana non trouvé" << std::endl;
    }

    // Exemple où il peut y avoir collision (dépend de la fonction de hachage et de l'implémentation)
    // L'influence des collisions se manifeste avec un grand nombre de données
    // et/ou une mauvaise fonction de hachage
    return 0;
}