É verdade que o tempo de busca de um elemento em unordered_set é constante?

Sim, em média, o tempo de busca de um elemento em std::unordered_set é constante — O(1).

Isto é conseguido através do uso de uma tabela de dispersão. A chave do elemento é hashada, e esse valor é usado para determinar a posição do elemento na tabela. Se a função de dispersão for boa e o número de colisões for mínimo, o acesso ao elemento é direto.

No entanto, no pior caso (quando há muitas colisões), o tempo de busca pode tornar-se linear — O(n), onde n é o número de elementos. Isto acontece quando todos ou a maioria dos elementos são hashados no mesmo "bucket" da tabela de dispersão, e a busca reduz-se a percorrer os elementos nesse bucket.

Fatores que afetam o desempenho:

• A qualidade da função de dispersão.
• O fator de carga (load factor) da tabela de dispersão (relação entre o número de elementos e o número de buckets). Um fator de carga elevado aumenta a probabilidade de colisões.

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

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

    // Procura de um elemento - em média O(1)
    if (mySet.count("banana")) {
        std::cout << "Encontrado banana" << std::endl;
    } else {
        std::cout << "Banana não encontrado" << std::endl;
    }

    // Exemplo onde pode haver colisão (depende da função de dispersão e implementação)
    // A influência das colisões manifesta-se com um grande número de dados
    // e/ou uma má função de dispersão
    return 0;
}