📚 دليل دراسة الجداول التجزئة

CS210 - الأسبوع 13 - مرجع شامل

1. مقدمة للجداول التجزئة

ما هي الخريطة؟

الخريطة هي هيكل بيانات يمثل مجموعة قابلة للبحث من أزواج المفتاح-القيمة، حيث:

• المفاتيح فريدة - لا يسمح بمفاتيح مكررة
• كل مفتاح يعين لـ قيمة واحدة بالضبط
• العمليات الرئيسية: get(key), put(key, value), remove(key)

2. التجزئة: الخطة الأساسية

الفكرة الأساسية

احفظ العناصر في جدول مفهرس بالمفتاح حيث يتم حساب الفهرس كدالة للمفتاح.

مقايضة المساحة-الزمن

3. دوال التجزئة

حساب رموز التجزئة

للأعداد الصحيحة

public int hashCode() { 
    return value; 
}

ببساطة أرجع قيمة العدد الصحيحة نفسها.

للبيانات المنطقية

public int hashCode() {
    if (value) return 1231;
    else return 1237;
}

استخدم عددين أوليين مختلفين لـ true و false.

للأعداد العشرية

public int hashCode() {
    long bits = doubleToLongBits(value);
    return (int) (bits ^ (bits >>> 32));
}

حول إلى تمثيل 64-بت وXOR النصفين.

للنصوص (طريقة هورنر)

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < length(); i++)
        hash = s[i] + (31 * hash);
    return hash;
}

hash = 99·31³ + 97·31² + 108·31 + 108
     = 108 + 31·(108 + 31·(97 + 31·99))
     = 3,045,982

التجزئة المعيارية

حول رمز التجزئة (أي عدد صحيح 32-بت) إلى فهرس جدول (0 إلى M-1):

private int hash(Key key) {
    return key.hashCode() % M;
}

private int hash(Key key) {
    return (key.hashCode() & 0x7fffffff) % M;
}

افتراض التجزئة الموحدة

مشكلة عيد الميلاد وموازنة الحمل

• مشكلة عيد الميلاد: توقع كرتين في نفس الصندوق بعد ~√(πM/2) رمية
• جامع القسائم: توقع كل صندوق به ≥1 كرة بعد ~M ln M رمية
• موازنة الحمل: بعد M رمية، معظم الصناديق المحملة لها Θ(log M / log log M) كرات

4. التسلسل المنفصل

كيف يعمل

1. تجزئة: عين المفتاح لعدد صحيح i بين 0 و M-1
2. إدراج: ضع في مقدمة السلسلة رقم i (إذا لم تكن موجودة بالفعل)
3. بحث: ابحث فقط في السلسلة رقم i

Array Index          Linked List Chain
    0         →     [A] → [B] → [E] → null
    1         →     null
    2         →     [X] → [S] → null
    3         →     null
    4         →     [L] → [P] → null
    5         →     [M] → [H] → [C] → [R] → null
            

تنفيذ جافا

public class SeparateChainingHashST<Key, Value> {
    private int M = 97;  // عدد السلاسل
    private Node[] st = new Node[M];  // مصفوفة السلاسل
    
    private static class Node {
        private Object key;
        private Object val;
        private Node next;
    }
    
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public Value get(Key key) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (key.equals(x.key))
                return (Value) x.val;
        return null;
    }
    
    public void put(Key key, Value val) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (keys[i].equals(key)) { 
                x.val = val; 
                return; 
            }
        st[i] = new Node(key, val, st[i]);
    }
}

تحليل الأداء

إستراتيجية تغيير الحجم

5. الفحص الخطي

كيف يعمل

1. تجزئة: عين المفتاح لعدد صحيح i بين 0 و M-1
2. إدراج: ضع في فهرس الجدول i إذا كان حراً؛ إذا لا، جرب i+1, i+2, إلخ.
3. بحث: ابحث في فهرس الجدول i؛ إذا كان مشغولاً ولكن لا تطابق، جرب i+1, i+2, إلخ.

Index:  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
       [P] [M] [ ] [ ] [A] [C] [S] [H] [L] [ ] [E] [ ] [ ] [ ] [R] [X]

Insert K: hash(K) = 5
          Position 5 occupied → try 6 → occupied → try 7 → occupied
          → try 8 → occupied → try 9 → EMPTY! Insert at 9
            

تنفيذ جافا

public class LinearProbingHashST<Key, Value> {
    private int M = 30001;
    private Value[] vals = (Value[]) new Object[M];
    private Key[] keys = (Key[]) new Object[M];
    
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i+1) % M)
            if (key.equals(keys[i]))
                return vals[i];
        return null;
    }
    
    public void put(Key key, Value val) {
        int i;
        for (i = hash(key); keys[i] != null; i = (i+1) % M)
            if (keys[i].equals(key))
                break;
        keys[i] = key;
        vals[i] = val;
    }
}

مشكلة وقوف كنوث

تحليل الأداء

الحذف في الفحص الخطي

الحل: بعد الحذف، يجب إعادة تجزئة جميع المفاتيح في نفس العنقود الذي يأتي بعد المفتاح المحذوف.

6. مقارنة الأداء

التسلسل المنفصل مقابل الفحص الخطي

مقارنة تنفيذات جدول الرموز الكاملة

* تحت افتراض التجزئة الموحدة

7. مواضيع متقدمة

متغيرات دوال التجزئة

تجزئة فحص مزدوج

تجزئة مزدوجة

h(x) = h1(x) + j·h2(x)  حيث j = 0, 1, 2, ...

تجزئة الوقواق

هجمات التعقيد الخوارزمي

"Aa" and "BB" both hash to 2112
"AaAa", "AaBB", "BBAa", "BBBB" all hash to -540425984
            

دوال التجزئة أحادية الاتجاه

8. الملخص وأفضل الممارسات

أفضل الممارسات

✅ افعل:

• استخدم أعداداً أولية أو قوى 2 لحجم الجدول M
• احتفظ بعامل الحمل α بين 0.5 و 0.75 للفحص الخطي
• احتفظ بعامل الحمل α حول 1-4 للتسلسل المنفصل
• نفذ hashCode() صحيحة تستخدم جميع الحقول المهمة
• تأكد من أن equals() و hashCode() متسقتان
• غير الحجم ديناميكياً للحفاظ على أداء جيد

❌ لا تفعل:

• استخدم دوال تجزئة قابلة للتنبؤ في التطبيقات الحساسة أمنياً
• تنسى التعامل مع بت الإشارة عند تحويل رموز التجزئة لفهارس
• احذف الإدخالات مباشرة في الفحص الخطي (يجب إعادة تجزئة العنقود)
• استخدم الجداول التجزئة إذا كنت تحتاج عمليات مرتبة (استخدم شجرة بحث ثنائية بدلاً من ذلك)
• تفترض تجزئة موحدة بدون اختبار دالة التجزئة الخاصة بك

متى تستخدم ماذا

المطبات الشائعة

مرجع سريع: تنفيذ رمز التجزئة

// قالب للأنواع المعرفة من المستخدم
public int hashCode() {
    int hash = 17;  // ثابت غير صفري
    hash = 31 * hash + field1.hashCode();  // نوع مرجعي
    hash = 31 * hash + ((Integer) field2).hashCode();  // بدائي
    hash = 31 * hash + field3.hashCode();  // نوع مرجعي
    return hash;
}