È vero che il tempo di ricerca di un elemento in unordered_set è costante?

Sì, in media, il tempo di ricerca di un elemento in std::unordered_set è costante — O(1).

Questo si ottiene grazie all'uso di una tabella hash. La chiave dell'elemento viene hashata, e questo valore viene usato per determinare la posizione dell'elemento nella tabella. Se la funzione hash è buona e il numero di collisioni è minimo, l'accesso all'elemento è diretto.

Tuttavia, nel caso peggiore (quando ci sono molte collisioni), il tempo di ricerca può diventare lineare — O(n), dove n è il numero di elementi. Questo accade quando tutti o la maggior parte degli elementi vengono hashati nello stesso "bucket" della tabella hash, e la ricerca si riduce a scorrere gli elementi in quel bucket.

Fattori che influenzano le prestazioni:

• La qualità della funzione hash.
• Il fattore di carico (load factor) della tabella hash (rapporto tra il numero di elementi e il numero di bucket). Un alto fattore di carico aumenta la probabilità di collisioni.

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

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

    // Ricerca di un elemento - in media O(1)
    if (mySet.count("banana")) {
        std::cout << "Trovato banana" << std::endl;
    } else {
        std::cout << "Banana non trovato" << std::endl;
    }

    // Esempio in cui possono verificarsi collisioni (dipende dalla funzione hash e dall'implementazione)
    // L'influenza delle collisioni si manifesta con grandi quantità di dati
    // e/o una cattiva funzione hash
    return 0;
}