¿Es correcto que el tiempo de búsqueda de un elemento en unordered_set es constante?

Sí, en promedio, el tiempo de búsqueda de un elemento en std::unordered_set es constante — O(1).

Esto se logra mediante el uso de una tabla hash. La clave del elemento se somete a una función hash, y esta se usa para determinar la posición del elemento en la tabla. Si la función hash es buena y las colisiones son mínimas, el acceso al elemento es directo.

Sin embargo, en el peor de los casos (cuando hay muchas colisiones), el tiempo de búsqueda puede volverse lineal — O(n), donde n es el número de elementos. Esto sucede cuando todos o la mayoría de los elementos se hash en el mismo "bucket" de la tabla hash, y la búsqueda se reduce a recorrer los elementos en ese bucket.

Factores que afectan el rendimiento:

• La calidad de la función hash.
• La tasa de carga (load factor) de la tabla hash (relación entre el número de elementos y el número de buckets). Un alto factor de carga aumenta la probabilidad de colisiones.

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

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

    // Búsqueda de un elemento - en promedio O(1)
    if (mySet.count("banana")) {
        std::cout << "Encontrado banana" << std::endl;
    } else {
        std::cout << "Banana no encontrado" << std::endl;
    }

    // Ejemplo donde puede haber colisión (depende de la función hash y la implementación)
    // La influencia de las colisiones se manifiesta con una gran cantidad de datos
    // y/o una mala función hash
    return 0;
}