C++ Academy · Pelajaran

Pertimbangan Performa

Bucket dan faktor muatan

Pertimbangan Performa adalah pelajaran C++ Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C++ Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C++ Academy mencakup 4 pelajaran total.

Cara Tabel Hash Menyimpan Data

Kontainer tidak terurut menyimpan larik bucket. Hash sebuah kunci memilih bucket; beberapa kunci dalam satu bucket membentuk rantai yang dicari secara linear.

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

Bucket yang Dipilih

bucket(key) memberi tahu indeks bucket tempat kunci dipetakan saat ini.

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

Faktor Muatan

Faktor muatan adalah size / bucket_count. Muatan yang lebih tinggi berarti rantai yang lebih panjang dan pencarian yang lebih lambat.

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

Faktor Muatan Maksimum

max_load_factor() adalah batasnya. Saat faktor muatan melampaui batas tersebut, tabel melakukan rehash ke lebih banyak 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;
}

Melakukan Rehash

Rehash membangun ulang tabel dengan lebih banyak bucket dan bersifat mahal. Rehash terjadi secara otomatis saat faktor muatan terlampaui.

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

Reserve untuk Menghindari Rehash

Jika Anda mengetahui ukurannya sebelumnya, panggil reserve(n) untuk mengalokasikan bucket terlebih dahulu dan menghindari rehash berulang.

#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 secara Langsung

rehash(n) menetapkan jumlah bucket minimal sebesar n. Gunakan reserve untuk jumlah elemen dan rehash untuk jumlah 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;
}

Memeriksa Ukuran Bucket

bucket_size(i) menunjukkan jumlah elemen yang berbagi bucket i, sehingga berguna untuk mendiagnosis tabrakan.

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

Kasus Terburuk adalah O(n)

Dengan hash buruk yang sering bertabrakan, semua kunci membentuk rantai dalam satu bucket dan operasi menurun menjadi waktu linear. Hash yang baik menjaga kinerja 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;
}

Menurunkan Faktor Muatan Maksimum

Menetapkan max_load_factor yang lebih rendah menukar memori dengan kecepatan: lebih sedikit tabrakan, tetapi lebih banyak 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;
}

Pembatalan Iterator

Rehash membuat iterator tidak valid, tetapi referensi dan pointer ke elemen tetap valid. Rencanakan perulangan Anda dengan tepat.

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

Pemeriksaan Singkat

Uji pemahaman Anda tentang kinerja tabel hash.

Ringkasan

Anda telah mempelajari cara kerja internal tabel hash:

kunci dipetakan ke wadah; tabrakan membentuk rantai
faktor muatan = size / bucket_count; jika melebihi max_load_factor, pengindeksan ulang akan dipicu
gunakan reserve untuk menghindari pengindeksan ulang; pengindeksan ulang membatalkan iterator, tetapi tidak membatalkan referensi

Kursus berikutnya: membaca dan menulis berkas dengan fstream.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Pertimbangan Performa” gratis?

Ya — teks lengkap “Pertimbangan Performa” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C++ Academy, upgrade ke CoddyKit PRO. Kursus C++ Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Pertimbangan Performa”?

Bucket dan faktor muatan Kamu berlatih C++ Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C++ Academy?

Tidak diperlukan pengalaman sebelumnya. C++ Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Pertimbangan Performa” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C++ Academy ini?

Ya. Setiap pelajaran C++ Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke C++ Academy