C++ Academy · Lektion

Prestandaöverväganden

Bucketar och belastningsfaktor

Lektion 4 av 413 steg

Prestandaöverväganden är en gratis lektion i C++ Academy på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för C++ Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C++ Academy innehåller totalt 4 lektioner.

Så lagrar hashtabeller data

En osorterad behållare innehåller en array av buckets. Hashvärdet för en nyckel väljer en bucket; flera nycklar i samma bucket bildar en kedja som söks igenom linjärt.

#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;
}

Vilken bucket

bucket(key) anger vilket bucket-index en nyckel för närvarande mappas till.

#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;
}

Belastningsfaktor

Belastningsfaktorn är size / bucket_count. En högre belastning innebär längre kedjor och långsammare sökningar.

#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;
}

Maximal belastningsfaktor

max_load_factor() är tröskelvärdet. När belastningsfaktorn överskrider det gör tabellen en rehashning till fler buckets.

#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;
}

Rehashning

Rehashning bygger om tabellen med fler buckets och är kostsam. Den sker automatiskt när belastningsfaktorn överskrids.

#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;
}

Använd reserve för att undvika rehashning

Om du känner till storleken i förväg kan du anropa reserve(n) för att förallokera buckets och undvika upprepade rehashningar.

#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;
}

rehash direkt

rehash(n) anger bucket-antalet till minst n. Använd reserve för antal element och rehash för antal buckets.

#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;
}

Inspektera bucketstorlekar

bucket_size(i) visar hur många element som delar bucket i, vilket är användbart för att diagnostisera kollisioner.

#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;
}

Värsta fallet är O(n)

Med en dålig hashfunktion som ger många kollisioner hamnar alla nycklar i en kedja i samma bucket, och operationerna försämras till linjär tid. En bra hashfunktion håller dem i 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;
}

Sänka maximal belastningsfaktor

Att ange en lägre max_load_factor byter minnesanvändning mot hastighet: färre kollisioner, men fler buckets.

#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;
}

Ogiltigförklaring av iteratorer

En rehashning ogiltigförklarar iteratorer, men håller referenser och pekare till elementen giltiga. Planera looparna därefter.

#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;
}

Snabbtest

Testa er förståelse av hashtabellers prestanda.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Ni har lärt er hur hashtabeller fungerar internt:

nycklar mappas till buckets; kollisioner bildar kedjor
load factor = storlek / bucket_count; om värdet överskrider max_load_factor utförs en rehash
använd reserve för att undvika rehashning; en rehash gör iteratorer ogiltiga men inte referenser

Nästa kurs: läsa och skriva filer med fstream.

Gratis att börja

Lär dig C++ med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 51
Lektioner: 203

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Prestandaöverväganden” gratis?

Ja – du kan läsa vilka 3 lektioner som helst i lärvägen C++ Academy, inklusive ”Prestandaöverväganden”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i C++ Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Prestandaöverväganden”?

Bucketar och belastningsfaktor Ni övar på C++ Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig C++ Academy?

Du behöver inga förkunskaper. Utbildningen i C++ Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.

Hur lång tid tar lektionen ”Prestandaöverväganden”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här C++ Academy-lektionen?

Ja. Varje C++ Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till C++ Academy