C++ Academy · Lekcja

Kwestie wydajności

Koszyki i współczynnik obciążenia

Kwestie wydajności to bezpłatna lekcja C++ Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C++ Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C++ Academy zawiera 4 lekcji w sumie.

Jak tablice haszujące przechowują dane

Kontener nieuporządkowany zawiera tablicę kubełków. Hasz klucza wybiera kubełek, a wiele kluczy w jednym kubełku tworzy łańcuch przeszukiwany liniowo.

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

Który kubełek?

bucket(key) informuje, do którego indeksu kubełka obecnie mapuje się dany klucz.

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

Współczynnik wypełnienia

Współczynnik wypełnienia to size / bucket_count. Większe wypełnienie oznacza dłuższe łańcuchy i wolniejsze wyszukiwanie.

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

Maksymalny współczynnik wypełnienia

max_load_factor() wyznacza próg. Gdy współczynnik wypełnienia go przekroczy, tablica wykonuje ponowne haszowanie, zwiększając liczbę kubełków.

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

Ponowne haszowanie

Ponowne haszowanie przebudowuje tablicę z większą liczbą kubełków i jest kosztowne. Następuje automatycznie po przekroczeniu współczynnika wypełnienia.

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

Rezerwowanie w celu uniknięcia ponownego haszowania

Jeśli rozmiar jest znany z wyprzedzeniem, należy wywołać reserve(n), aby wstępnie przydzielić kubełki i uniknąć wielokrotnego ponownego haszowania.

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

Bezpośrednie użycie rehash

rehash(n) ustawia liczbę kubełków na co najmniej n. reserve służy do określania liczby elementów, a rehash do określania liczby kubełków.

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

Sprawdzanie rozmiarów kubełków

bucket_size(i) pokazuje, ile elementów współdzieli kubełek i, co jest przydatne podczas diagnozowania kolizji.

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

Najgorszy przypadek to O(n)

Przy nieprawidłowej funkcji haszującej powodującej wiele kolizji wszystkie klucze tworzą łańcuch w jednym kubełku, a złożoność operacji spada do czasu liniowego. Dobra funkcja haszująca pozwala zachować 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;
}

Zmniejszanie maksymalnego współczynnika wypełnienia

Ustawienie niższej wartości max_load_factor wymienia pamięć na szybkość: oznacza mniej kolizji, ale więcej kubełków.

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

Unieważnianie iteratorów

Ponowne haszowanie unieważnia iteratory, ale zachowuje ważność referencji i wskaźników do elementów. Należy odpowiednio zaplanować pętle.

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

Szybki test

Proszę sprawdzić swoją wiedzę na temat wydajności tablic haszujących.

Podsumowanie

Poznali Państwo wewnętrzne mechanizmy tablic haszujących:

klucze są mapowane na kubełki, a kolizje tworzą łańcuchy
współczynnik zapełnienia = size / bucket_count; po przekroczeniu max_load_factor następuje ponowne haszowanie
należy używać reserve, aby uniknąć ponownego haszowania; ponowne haszowanie unieważnia iteratory, ale nie referencje

Następny kurs: odczytywanie i zapisywanie plików za pomocą fstream.

Często zadawane pytania

Czy lekcja „Kwestie wydajności” jest bezpłatna?

Tak — pełny tekst „Kwestie wydajności” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C++ Academy, przejdź na CoddyKit PRO. Kurs C++ Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Kwestie wydajności”?

Koszyki i współczynnik obciążenia Ćwiczysz C++ Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C++ Academy?

Nie wymagamy żadnego doświadczenia. C++ Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Kwestie wydajności”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C++ Academy?

Tak. Każda lekcja C++ Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C++ Academy