C Academy · درس

معالجة التصادمات

الربط والاستقصاء

معالجة التصادمات درس مجاني في C Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 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;
}

تحقق سريع

اختبروا معرفتكم بكيفية التعامل مع التصادمات.

مراجعة

استكشفتم كيفية حل جداول التجزئة للتصادمات.

تخزّن السلاسل قائمة مترابطة لكل خانة
تبحث العنونة المفتوحة بالفحص عن خانة فارغة
أشكال الفحص: الخطي والتربيعي والتجزئة المزدوجة
تحتاج العنونة المفتوحة إلى علامات الحذف لتنفيذ الحذف

الأسئلة الشائعة

هل درس «معالجة التصادمات» مجاني؟

نعم — نص درس «معالجة التصادمات» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة C Academy، انتقل إلى CoddyKit PRO. تتضمن دورة C Academy 4 دروس في المجموع.

ماذا ستتعلم في «معالجة التصادمات»؟

الربط والاستقصاء تتمرن على C Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ C Academy؟

لا تُشترط خبرة سابقة. C Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.

كم من الوقت يستغرق درس «معالجة التصادمات»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس C Academy هذا؟

نعم. كل درس في C Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

← العودة إلى C Academy