C Academy · บทเรียน

การจัดการการชนกัน

การเชื่อมโยงและการตรวจสอบตำแหน่ง

การจัดการการชนกัน เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

ปัญหาการชนกัน

การชนกันเกิดขึ้นเมื่อคีย์ที่แตกต่างกันสองคีย์ได้ค่าแฮชไปยังช่องเก็บเดียวกัน เนื่องจากการชนกันหลีกเลี่ยงไม่ได้ ตารางแฮชทุกตารางจึงต้องมีกลยุทธ์สำหรับจัดเก็บคีย์หลายคีย์ในช่องเดียว

แนวทางหลักมีสองกลุ่ม ได้แก่ การทำสายโซ่และการระบุตำแหน่งแบบเปิด

การเชื่อมโยงแบบแยก

สำหรับการเชื่อมโยงแบบแยก แต่ละช่องจะเก็บรายการแบบเชื่อมโยงของรายการข้อมูล เมื่อเกิดการชนกัน คุณเพียงเพิ่มรายการต่อท้าย (หรือนำไปต่อไว้ด้านหน้า) ของรายการในช่องนั้น

ช่องเก็บตัวชี้ไปยังหัวรายการ
การค้นหาจะเดินผ่านรายการสั้น ๆ เพียงรายการเดียว

โครงสร้างโหนดของการเชื่อมโยง

แต่ละโหนดจะเก็บคีย์ ค่า และตัวชี้ next ตารางเป็นอาร์เรย์ของตัวชี้ไปยังโหนด

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

การแทรกด้วยการเชื่อมโยง

การเพิ่มรายการไว้ด้านหน้าของรายการในช่องใช้เวลา O(1) ในที่นี้เราจะสร้างสายโซ่ขนาดเล็กด้วยตนเองและพิมพ์ผลออกมา

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

การระบุตำแหน่งแบบเปิด

สำหรับการระบุตำแหน่งแบบเปิด รายการข้อมูลทุกตัวจะอยู่โดยตรงในอาร์เรย์ช่อง เมื่อเกิดการชนกัน คุณจะตรวจสอบช่องว่างอื่นตามลำดับที่กำหนดไว้

ไม่มีการจัดสรรโหนดเพิ่มเติม จึงใช้แคชได้ดี

การตรวจสอบเชิงเส้น

การตรวจสอบเชิงเส้นจะตรวจสอบช่องถัดไป แล้วตรวจสอบช่องถัดไปเรื่อย ๆ โดยวนกลับไปต้นอาร์เรย์เมื่อถึงท้ายอาร์เรย์: (h + i) % capacity

วิธีนี้เรียบง่ายและใช้แคชได้ดี แต่เกิดการกระจุกตัวได้ง่าย

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

การตรวจสอบกำลังสอง

การตรวจสอบกำลังสองใช้ (h + i*i) % capacity เพื่อกระจายตำแหน่งที่ตรวจสอบและลดการกระจุกตัวหลัก

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

การแฮชสองชั้น

การแฮชสองชั้นใช้ค่าแฮชที่สองกำหนดระยะก้าว: (h1 + i*h2) % capacity วิธีนี้ทำให้แต่ละคีย์มีลำดับการตรวจสอบของตนเอง และให้การกระจายที่ดีที่สุดในสามวิธี

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

การลบในการระบุตำแหน่งแบบเปิด

คุณไม่สามารถล้างช่องในการระบุตำแหน่งแบบเปิดได้โดยตรง เพราะจะทำให้สายโซ่การตรวจสอบของคีย์อื่นขาด แทนที่จะทำเช่นนั้น ให้ทำเครื่องหมายเป็นช่องหลุมศพ เพื่อให้การค้นหายังคงตรวจสอบช่องถัดไป

การเชื่อมโยงเทียบกับการระบุตำแหน่งแบบเปิด

ข้อแลกเปลี่ยน:

การเชื่อมโยง: รองรับอัตราการใช้งานสูง ลบได้ง่าย แต่ใช้ตัวชี้และมีการจัดสรรหน่วยความจำ
การระบุตำแหน่งแบบเปิด: ใช้แคชได้ดี ไม่ต้องจัดสรรหน่วยความจำให้แต่ละรายการ แต่ประสิทธิภาพลดลงมากเมื่อใกล้เต็ม และต้องใช้ช่องหลุมศพ

การสาธิตจำนวนครั้งที่ตรวจสอบ

การตรวจสอบเชิงเส้นอาจต้องใช้หลายขั้นเมื่อช่องเกิดการกระจุกตัว ในที่นี้เราจะนับจำนวนครั้งที่ตรวจสอบเพื่อค้นหาช่องว่าง

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

ตรวจสอบความเข้าใจ

ทดสอบความรู้ของคุณเกี่ยวกับการจัดการการชนกัน

สรุปทบทวน

คุณได้สำรวจวิธีที่ตารางแฮชใช้แก้ไขการชนกัน

การเชื่อมโยงเก็บรายการแบบเชื่อมโยงหนึ่งรายการต่อช่อง
การระบุตำแหน่งแบบเปิดตรวจสอบหาช่องว่าง
รูปแบบการตรวจสอบ: เชิงเส้น กำลังสอง และแฮชสองชั้น
การระบุตำแหน่งแบบเปิดต้องใช้ช่องหลุมศพสำหรับการลบ

คำถามที่พบบ่อย

บทเรียน “การจัดการการชนกัน” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การจัดการการชนกัน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การจัดการการชนกัน”

การเชื่อมโยงและการตรวจสอบตำแหน่ง คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “การจัดการการชนกัน” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy