C Academy · Pelajaran

Penanganan Collision

Chaining dan probing.

Penanganan Collision adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 2 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.

Masalah Tabrakan

Tabrakan terjadi saat dua kunci berbeda menghasilkan hash ke bucket yang sama. Karena tabrakan tidak dapat dihindari, setiap tabel hash memerlukan strategi untuk menyimpan beberapa kunci dalam satu slot.

Dua kelompok utama strategi tersebut adalah rantai dan pengalamatan terbuka.

Pengaitan Terpisah

Dengan pengaitan terpisah, setiap ember menyimpan daftar tertaut berisi entri. Saat terjadi tabrakan, Anda cukup menambahkan entri di akhir (atau awal) daftar ember tersebut.

Ember menyimpan kepala daftar
Pencarian menelusuri satu daftar pendek

Struktur Simpul Pengaitan

Setiap simpul menyimpan kunci, nilai, dan penunjuk next. Tabel tersebut berupa larik penunjuk simpul.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

Menyisipkan dengan Pengaitan

Menambahkan di awal daftar ember membutuhkan O(1). Di sini kita membuat rantai kecil secara manual lalu mencetaknya.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

Pengalamatan Terbuka

Dengan pengalamatan terbuka, setiap entri berada langsung di dalam larik ember. Saat terjadi tabrakan, Anda memeriksa slot kosong lain menggunakan urutan tetap.

Tidak ada simpul tambahan yang dialokasikan, sehingga penggunaan tembolok menjadi efisien.

Pemeriksaan Linear

Pemeriksaan linear memeriksa slot berikutnya, lalu slot setelahnya, dan kembali ke awal jika mencapai ujung: (h + i) % capacity.

Metode ini sederhana dan efisien bagi tembolok, tetapi mengalami pengelompokan.

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

Pemeriksaan Kuadratik

Pemeriksaan kuadratik menggunakan (h + i*i) % capacity untuk menyebarkan pemeriksaan dan mengurangi pengelompokan utama.

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

Pengacakan Ganda

Pengacakan ganda menggunakan fungsi hash kedua untuk menentukan ukuran langkah: (h1 + i*h2) % capacity. Dengan demikian, setiap kunci memiliki urutan pemeriksaannya sendiri dan distribusi terbaik di antara ketiga metode.

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

Penghapusan dalam Pengalamatan Terbuka

Anda tidak bisa begitu saja mengosongkan slot dalam pengalamatan terbuka karena hal itu akan memutus rantai pemeriksaan untuk kunci lain. Sebagai gantinya, tandai slot tersebut dengan penanda penghapusan agar pencarian tetap memeriksa slot setelahnya.

Pengaitan vs Pengalamatan Terbuka

Keunggulan dan kekurangan:

Pengaitan: menangani faktor muatan tinggi dan penghapusan sederhana, tetapi menggunakan penunjuk dan alokasi
Pengalamatan terbuka: efisien bagi tembolok dan tidak memerlukan alokasi per entri, tetapi kinerjanya menurun drastis saat hampir penuh serta memerlukan penanda penghapusan

Demonstrasi Jumlah Pemeriksaan

Pemeriksaan linear dapat memerlukan beberapa langkah ketika slot-slot mengelompok. Di sini kita menghitung pemeriksaan untuk menemukan slot kosong.

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

Pemeriksaan Singkat

Uji pengetahuan Anda tentang penanganan tabrakan.

Ringkasan

Anda telah mempelajari cara tabel hash menyelesaikan tabrakan.

Pengaitan menyimpan daftar tertaut untuk setiap ember
Pengalamatan terbuka memeriksa slot kosong
Variasi pemeriksaan: linear, kuadratik, dan pengacakan ganda
Pengalamatan terbuka memerlukan penanda penghapusan untuk penghapusan

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Penanganan Collision” gratis?

Ya — teks lengkap “Penanganan Collision” 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 “Penanganan Collision”?

Chaining dan probing. 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 2 dari 4.

Berapa lama pelajaran “Penanganan Collision” 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