Pengubahan Ukuran dan Faktor Muatan
Penyetelan performa.
Pengubahan Ukuran dan Faktor Muatan 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.
Apa Itu Faktor Muatan
Faktor muatan adalah rasio entri yang disimpan terhadap jumlah ember: alpha = size / capacity. Faktor ini mengukur tingkat kepenuhan tabel dan secara langsung memengaruhi kinerja.
Mengapa Faktor Muatan Penting
Saat faktor muatan meningkat, ember menyimpan rantai yang lebih panjang (atau pemeriksaan semakin mengelompok), sehingga operasi menjadi lebih lambat.
- Alpha rendah: cepat, tetapi memboroskan memori
- Alpha tinggi: hemat tempat, tetapi lambat
Sasaran yang umum untuk pengaitan adalah 0.75.
Menghitung Faktor Muatan
Hitung faktor tersebut sebagai rasio titik-mengambang agar Anda dapat membandingkannya dengan ambang batas.
#include <stdio.h>
int main(void) {
unsigned size = 12, capacity = 16;
double alpha = (double)size / capacity;
printf("load factor = %.2f\n", alpha);
return 0;
}Kapan Harus Mengubah Ukuran
Setelah setiap penyisipan, periksa apakah faktor muatan melampaui ambang batas. Jika ya, perbesar tabel (biasanya dengan menggandakan kapasitas) lalu lakukan hash ulang.
#include <stdio.h>
int should_grow(unsigned size, unsigned cap) {
return (double)size / cap > 0.75;
}
int main(void) {
printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
printf("%d\n", should_grow(10, 16)); /* 0.625 -> 0 */
return 0;
}Penjelasan Hash Ulang
Anda tidak dapat menyalin ember begitu saja karena indeks setiap kunci bergantung pada kapasitas. Hash ulang menghitung kembali ember setiap kunci berdasarkan kapasitas baru, lalu menyisipkannya kembali.
Fungsi Pengubahan Ukuran
Alokasikan larik ember baru yang lebih besar; telusuri setiap simpul lama dan pindahkan ke larik baru menggunakan kapasitas baru; kemudian tukar kedua larik tersebut. Berikut perhitungan ulang indeks intinya.
#include <stdio.h>
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
int main(void) {
const char *key = "session";
unsigned old_cap = 8, new_cap = 16;
printf("old slot = %lu\n", djb2(key) % old_cap);
printf("new slot = %lu\n", djb2(key) % new_cap);
return 0;
}Memindahkan Simpul Tanpa Alokasi Ulang
Dengan pengaitan, Anda dapat memindahkan simpul yang sudah ada ke larik baru tanpa mengalokasikan simpul baru. Lepaskan setiap simpul, hitung kembali embernya, lalu tambahkan di awal.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
int main(void) {
Node *old[2] = {0};
Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
Node *new_b[4] = {0};
/* move node a */
unsigned i = djb2(a->key) % 4;
a->next = new_b[i]; new_b[i] = a;
printf("moved to slot %u\n", i);
return 0;
}Strategi Pertumbuhan
Menggandakan kapasitas mempertahankan biaya penyisipan teramortisasi O(1): meskipun pengubahan ukuran membutuhkan O(n), operasi ini cukup jarang sehingga biaya rata-rata per penyisipan tetap konstan.
Pangkat dua juga memungkinkan Anda menggunakan masker AND yang cepat.
#include <stdio.h>
int main(void) {
unsigned cap = 8;
for (int i = 0; i < 4; i++) {
printf("capacity = %u\n", cap);
cap *= 2;
}
return 0;
}Penyusutan
Anda dapat menyusutkan tabel ketika faktor muatan turun terlalu rendah (misalnya di bawah 0.1) setelah banyak penghapusan. Penyusutan mengembalikan memori, tetapi menambah biaya hash ulang, jadi lakukan secara hati-hati agar tidak terjadi perubahan ukuran berulang-ulang.
Pengalamatan Terbuka dan Faktor Muatan
Tabel pengalamatan terbuka jauh lebih sensitif terhadap faktor muatan. Kinerja merosot saat alpha mendekati 1, sehingga tabel biasanya diubah ukurannya pada 0.5 hingga 0.7, lebih rendah daripada 0.75 pada pengaitan.
Demonstrasi Biaya Teramortisasi
Simulasikan penyisipan yang menggandakan kapasitas pada 0.75 dan hitung total pekerjaannya untuk menunjukkan bahwa rata-ratanya tetap rendah.
#include <stdio.h>
int main(void) {
unsigned cap = 4, size = 0;
long work = 0;
for (int i = 0; i < 100; i++) {
size++; work++; /* the insert */
if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
}
printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
return 0;
}Pemeriksaan Singkat
Uji pemahaman Anda tentang pengubahan ukuran.
Ringkasan
Anda telah mempelajari cara menyesuaikan kinerja tabel hash.
- Faktor muatan = ukuran / kapasitas
- Ubah ukuran ketika faktor tersebut melampaui ambang batas (sekitar 0.75 untuk pengaitan)
- Lakukan hash ulang karena indeks bergantung pada kapasitas
- Penggandaan kapasitas menghasilkan penyisipan teramortisasi O(1)
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pengubahan Ukuran dan Faktor Muatan” gratis?
Ya — teks lengkap “Pengubahan Ukuran dan Faktor Muatan” 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 “Pengubahan Ukuran dan Faktor Muatan”?
Penyetelan performa. 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 “Pengubahan Ukuran dan Faktor Muatan” 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
- Fungsi Hash
- Penanganan Collision
- Sisipkan, Cari, Hapus
- Pengubahan Ukuran dan Faktor Muatan