C++ Academy · Lezione

Considerazioni sulle prestazioni

Bucket e fattore di carico

Considerazioni sulle prestazioni è una lezione C++ Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C++ Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C++ Academy include 4 lezioni in totale.

Come le tabelle hash memorizzano i dati

Un contenitore unordered contiene un array di bucket. L'hash di una chiave seleziona un bucket; più chiavi nello stesso bucket formano una catena che viene cercata linearmente.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}, {3, 3}};
    std::cout << "bucket count: " << m.bucket_count() << '\n';
    return 0;
}

Quale bucket?

bucket(key) indica l'indice del bucket a cui è attualmente associata una chiave.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{10, 1}, {20, 2}, {30, 3}};
    std::cout << "key 20 in bucket " << m.bucket(20) << '\n';
    return 0;
}

Fattore di carico

Il fattore di carico è size / bucket_count. Un carico maggiore comporta catene più lunghe e ricerche più lente.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}};
    std::cout << "load factor: " << m.load_factor() << '\n';
    return 0;
}

Fattore di carico massimo

max_load_factor() è la soglia. Quando il fattore di carico la supera, la tabella esegue il rehash creando più bucket.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "default max load: " << m.max_load_factor() << '\n';
    return 0;
}

Rehash

Il rehash ricostruisce la tabella con più bucket ed è costoso. Viene eseguito automaticamente quando il fattore di carico supera la soglia.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::size_t before = m.bucket_count();
    for (int i = 0; i < 100; ++i) m[i] = i;
    std::cout << before << " -> " << m.bucket_count() << " buckets\n";
    return 0;
}

Riservare spazio per evitare il rehash

Se conosce in anticipo le dimensioni, chiami reserve(n) per preallocare i bucket ed evitare rehash ripetuti.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    std::cout << "buckets reserved: " << (m.bucket_count() >= 1000 ? "yes" : "no") << '\n';
    return 0;
}

Eseguire direttamente il rehash

rehash(n) imposta il numero di bucket su almeno n. Usi reserve per il numero di elementi e rehash per il numero di bucket.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.rehash(64);
    std::cout << "buckets >= 64: " << (m.bucket_count() >= 64 ? "yes" : "no") << '\n';
    return 0;
}

Esaminare le dimensioni dei bucket

bucket_size(i) rivela quanti elementi condividono il bucket i, risultando utile per diagnosticare le collisioni.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10; ++i) m[i] = i;
    std::cout << "bucket 0 holds " << m.bucket_size(0) << " elements\n";
    return 0;
}

Il caso peggiore è O(n)

Con un hash inefficace che genera molte collisioni, tutte le chiavi formano una catena in un unico bucket e le operazioni degradano a un tempo lineare. Un buon hash mantiene le operazioni su O(1).

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 5; ++i) m[i] = i * i;
    std::cout << "avg lookups stay fast with good hashing\n";
    std::cout << "load: " << m.load_factor() << '\n';
    return 0;
}

Ridurre il fattore di carico massimo

Impostare un max_load_factor più basso sacrifica memoria a vantaggio della velocità: meno collisioni, ma più bucket.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.max_load_factor(0.5f);
    std::cout << "new max load: " << m.max_load_factor() << '\n';
    return 0;
}

Invalidazione degli iteratori

Un rehash invalida gli iteratori, ma mantiene validi i riferimenti e i puntatori agli elementi. Pianifichi i cicli di conseguenza.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 100}};
    int& ref = m[1];
    m.reserve(500);
    std::cout << "reference still valid: " << ref << '\n';
    return 0;
}

Verifica rapida

Verifichi la Sua comprensione delle prestazioni delle tabelle hash.

Riepilogo

Ha imparato i dettagli interni delle tabelle hash:

le chiavi vengono associate ai bucket; le collisioni formano catene
il fattore di carico = size / bucket_count; il superamento di max_load_factor attiva un rehash
usi reserve per evitare il rehash; un rehash invalida gli iteratori, ma non i riferimenti

Corso successivo: lettura e scrittura di file con fstream.

Domande Frequenti

La lezione «Considerazioni sulle prestazioni» è gratuita?

Sì — il testo completo di «Considerazioni sulle prestazioni» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C++ Academy, passa a CoddyKit PRO. Il corso C++ Academy include 4 lezioni in totale.

Cosa imparerò in «Considerazioni sulle prestazioni»?

Bucket e fattore di carico Eserciti C++ Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C++ Academy?

Non è richiesta alcuna esperienza precedente. C++ Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Considerazioni sulle prestazioni»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C++ Academy?

Sì. Ogni lezione C++ Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C++ Academy