PricingLoginStart free
C Academy · Pelajaran

Pengendalian Perlanggaran

Perantaian dan prob

Pelajaran 2 daripada 413 langkah

Pengendalian Perlanggaran ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Masalah Perlanggaran

Perlanggaran berlaku apabila dua kunci berbeza menghasilkan hash kepada bakul yang sama. Oleh sebab perlanggaran tidak dapat dielakkan, setiap jadual hash memerlukan strategi untuk menyimpan berbilang kunci dalam satu slot.

Dua kelompok utama ialah perantaian dan pengalamatan terbuka.

Rantaian Berasingan

Dengan rantaian berasingan, setiap baldi menyimpan senarai terpaut entri. Apabila berlaku perlanggaran, anda hanya perlu menambah pada hujung (atau pangkal) senarai baldi itu.

  • Baldi menyimpan kepala senarai
  • Pencarian menelusuri satu senarai pendek

Struktur Nod Rantaian

Setiap nod menyimpan kunci, nilai dan penuding next. Jadual ialah tatasusunan penuding nod.

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

Penyisipan dengan Rantaian

Menambah pada pangkal senarai baldi mengambil masa O(1). Di sini kita membina rantaian kecil secara manual dan 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 secara langsung dalam tatasusunan baldi. Apabila berlaku perlanggaran, anda memeriksa slot kosong lain menggunakan urutan tetap.

Tiada nod tambahan diperuntukkan, jadi kaedah ini mesra cache.

Pemeriksaan Linear

Pemeriksaan linear menyemak slot seterusnya, kemudian slot selepasnya, dan kembali ke awal apabila sampai ke penghujung: (h + i) % capacity.

Kaedah ini mudah dan mesra cache, 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 mengurangkan 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;
}

Pencincangan Berganda

Pencincangan berganda menggunakan cincangan kedua untuk saiz langkah: (h1 + i*h2) % capacity. Kaedah ini memberikan setiap kunci urutan pemeriksaan tersendiri serta taburan terbaik antara ketiga-tiganya.

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

Pemadaman dalam Pengalamatan Terbuka

Anda tidak boleh mengosongkan slot begitu sahaja dalam pengalamatan terbuka kerana tindakan itu akan memutuskan rantaian pemeriksaan untuk kunci lain. Sebaliknya, tandakannya sebagai penanda pemadaman supaya pencarian terus memeriksa slot selepasnya.

Rantaian berbanding Pengalamatan Terbuka

Pertukaran kelebihan dan kekurangan:

  • Rantaian: mengendalikan faktor muatan yang tinggi dan pemadaman yang mudah, tetapi menggunakan penuding dan peruntukan
  • Pengalamatan terbuka: mesra cache dan tiada peruntukan bagi setiap entri, tetapi merosot dengan ketara apabila hampir penuh serta memerlukan penanda pemadaman

Demonstrasi Bilangan Pemeriksaan

Pemeriksaan linear mungkin memerlukan beberapa langkah apabila slot berkelompok. Di sini kita mengira pemeriksaan yang diperlukan untuk mencari 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;
}

Semakan Pantas

Uji pengetahuan anda tentang pengendalian perlanggaran.

Jawab dalam pelajaran interaktif

Imbas Kembali

Anda telah meneroka cara jadual cincangan menyelesaikan perlanggaran.

  • Rantaian menyimpan senarai terpaut bagi setiap baldi
  • Pengalamatan terbuka memeriksa slot kosong
  • Variasi pemeriksaan: linear, kuadratik dan pencincangan berganda
  • Pengalamatan terbuka memerlukan penanda pemadaman untuk pemadaman
Percuma untuk bermula

Pelajari C dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
39
Pelajaran
144
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Pengendalian Perlanggaran” percuma?

Ya — teks penuh “Pengendalian Perlanggaran” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Pengendalian Perlanggaran”?

Perantaian dan prob Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan C Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Pengendalian Perlanggaran” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Fungsi Cincangan
  2. Pengendalian Perlanggaran
  3. Sisip, Cari, Padam
  4. Pelarasan Saiz dan Faktor Muatan
← Kembali ke C Academy