C Academy · درس

دوال التجزئة

تعيين المفاتيح إلى الحاويات

دوال التجزئة درس مجاني في C Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في C Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة C Academy 4 دروس في المجموع.

ما هي دالة التجزئة

تأخذ دالة التجزئة مفتاحًا وتنتج فهرسًا صحيحًا داخل مصفوفة من الحاويات. وهي جوهر جدول التجزئة، إذ تحوّل مفاتيح عشوائية مثل السلاسل النصية إلى مواضع سريعة في المصفوفة.

الإدخال: مفتاح (سلسلة نصية، عدد صحيح، وغير ذلك)
الإخراج: فهرس حاوية ضمن [0, capacity)

خصائص دالة التجزئة الجيدة

تكون دالة التجزئة الجيدة حتمية وسريعة، وتوزّع المفاتيح بانتظام على الحاويات.

يعطي المفتاح نفسه الفهرس نفسه دائمًا
تؤدي التغييرات الصغيرة في المفتاح إلى تغييرات كبيرة في الفهرس (تأثير الانهيار الجليدي)
عدد قليل من التصادمات مع البيانات المعتادة

التعيين إلى حاوية

بعد حساب قيمة التجزئة الخام، عيّنها إلى موضع في الجدول باستخدام عامل باقي القسمة: index = hash % capacity.

استخدم نوعًا unsigned حتى لا ينتج عن باقي القسمة فهرس سالب.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16;
    unsigned index = (unsigned)(hash % capacity);
    printf("bucket = %u\n", index);
    return 0;
}

دالة تجزئة بسيطة تعتمد على الجمع

تجمع أبسط دالة تجزئة للسلاسل النصية قيم الأحرف. وهي سهلة، لكنها توزّع القيم توزيعًا ضعيفًا لأن الكلمات التي تتكون من الأحرف نفسها بترتيب مختلف تؤدي إلى تصادمات.

شغّلها لترى سلسلتين نصيتين مختلفتين تنتجان قيمتي تجزئة متقاربتين.

#include <stdio.h>

unsigned long sum_hash(const char *s) {
    unsigned long h = 0;
    while (*s) h += (unsigned char)*s++;
    return h;
}

int main(void) {
    printf("%lu\n", sum_hash("abc"));
    printf("%lu\n", sum_hash("cba"));
    return 0;
}

دالة تجزئة DJB2

تُعد DJB2 دالة تجزئة كلاسيكية للسلاسل النصية، ذات توزيع جيد، طوّرها Daniel J. Bernstein. تبدأ من 5381 وتستخدم hash * 33 + c.

يمزج الضرب والجمع البتات بكفاءة أكبر بكثير من الجمع العادي.

#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; /* h * 33 + c */
    return h;
}

int main(void) {
    printf("%lu\n", djb2("hello"));
    printf("%lu\n", djb2("world"));
    return 0;
}

دالة تجزئة FNV-1a

تطبّق FNV-1a عملية XOR على كل بايت، ثم تضرب الناتج في عدد أولي. وهي بسيطة وسريعة وشائعة الاستخدام.

الترتيب هو: XOR أولًا، ثم الضرب (وهذا ما يميز الصيغة 1a).

#include <stdio.h>

unsigned long fnv1a(const char *s) {
    unsigned long h = 1469598103934665603UL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211UL;
    }
    return h;
}

int main(void) {
    printf("%lu\n", fnv1a("key1"));
    printf("%lu\n", fnv1a("key2"));
    return 0;
}

تجزئة الأعداد الصحيحة

تحتاج مفاتيح الأعداد الصحيحة أيضًا إلى المزج، لأن استخدام x % capacity وحده يؤدي إلى تكتل القيم عندما تشترك المفاتيح في أنماط معينة. وينشر المزج الضربي (Knuth) البتات.

#include <stdio.h>

unsigned hash_int(unsigned x, unsigned cap) {
    x *= 2654435761u; /* Knuth multiplicative */
    return x % cap;
}

int main(void) {
    for (unsigned i = 0; i < 5; i++)
        printf("%u -> %u\n", i, hash_int(i, 8));
    return 0;
}

الأحجام التي تمثل قوى العدد 2

عندما تكون السعة قوةً للعدد 2، يمكنك استبدال % capacity بعملية AND سريعة على مستوى البتات: hash & (capacity - 1).

ينجح ذلك لأن البتات منخفضة الترتيب في العدد الذي ينقص واحدًا عن قوة للعدد 2 تكوّن قناعًا كاملًا.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16; /* power of two */
    unsigned index = (unsigned)(hash & (capacity - 1));
    printf("bucket = %u\n", index);
    return 0;
}

لماذا قد يكون باقي القسمة بطيئًا

يُترجم العامل % إلى تعليمة قسمة، وهي أبطأ من AND. ويكون ذلك مهمًا في الحلقات المكثفة.

جدول بسعة تمثل قوة للعدد 2: استخدم قناع AND
جدول بحجم أولي: استخدم باقي القسمة (لتوزيع أفضل مع دوال التجزئة الضعيفة)

التصادمات حتمية

وفقًا لـمبدأ الحمام، يضمن تعيين مفاتيح كثيرة إلى عدد أقل من الحاويات حدوث تصادمات. تقلل دالة التجزئة الجيدة من التصادمات، لكنها لا تستطيع إزالتها تمامًا.

يغطي الدرس التالي كيفية معالجة التصادمات.

عرض توضيحي للتوزيع

لنعدّ كيفية توزيع DJB2 لعدد قليل من المفاتيح على 8 حاويات. توزّع دوال التجزئة الجيدة القيم توزيعًا متقاربًا.

#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 *keys[] = {"apple", "banana", "cherry", "date"};
    int counts[8] = {0};
    for (int i = 0; i < 4; i++)
        counts[djb2(keys[i]) % 8]++;
    for (int i = 0; i < 8; i++)
        printf("bucket %d: %d\n", i, counts[i]);
    return 0;
}

تحقق سريع

اختبر مدى فهمك لأساسيات دوال التجزئة.

مراجعة

تعلّمت وظيفة دالة التجزئة وكيفية تعيين المفاتيح إلى الحاويات.

تكون دوال التجزئة الجيدة حتمية وسريعة ومنتظمة
تُعد DJB2 وFNV-1a دالتي تجزئة جيدتين للسلاسل النصية
عيّن باستخدام % capacity، أو باستخدام & (capacity-1) عندما تكون السعة قوة للعدد 2
استخدم أنواعًا unsigned؛ فالتصادمات لا يمكن تجنبها

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

هل درس «دوال التجزئة» مجاني؟

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

ماذا ستتعلم في «دوال التجزئة»؟

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

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

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

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

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

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

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

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

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