التجزئة
| English | العربية |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | دالة التجزئة |
| key/kiː/ | بحث مفتاح القاموس إلى القيمة؛ التفاصيل في البطاقات أدناه. |
| address/əˈdres/ | العنوان |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | حتمي |
| collision/kəˈlɪʒn/ | اصطدام |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | التفتيش الخطي |
| chaining/ˈtʃeɪnɪŋ/ | السلاسل المترابطة |
| load factor/ləʊd ˈfæktə/ | معامل التحميل |
إيجاد صف واحد من خمسين مليوناً دون النظر
- كاشير سوبر ماركت يمسح رمز شريطي ويظهر السعر قبل أن ترفع يدك عن المنتج. ملف المنتجات يحتوي على خمسين مليون سطر.
- لم يتم البحث عنهم جميعاً. ذهب رقم الرمز الشريطي عبر عملية حسابية قصيرة أنتجت موقعاً، وقارأ الكمبيوتر ذلك الموقع: قراءة واحدة، بدون مقارنات، نفس الوقت سواء كان الملف يحتوي على خمسين صفاً أو خمسين مليوناً.
- العملية الحسابية هي دالة تجعيد (Hash function)، والفكرة بأكملها تعتمد عليها: لا تخزن البيانات حيث ستسعدها، بل خزنها حيث يقول مفتاحها الخاص أنها تنتمي إليها.
- هذا الدرس يتعلق بخوارزميات التجعيد، وما يحدث عندما يريد مفتاحان نفس الشغرة، وكيف نبحث ونُدرج.
دالة التجعيد
- دالة التجعيد، أو خوارزمية التجعيد، تأخذ مفتاح السجل وتنتج العنوان الذي يُخزن فيه السجل.
- الجيدة منها سريعة، حتمية (نفس المفتاح يعطي دائماً نفس العنوان)، وتوزع المفاتيح بشكل متساوٍ عبر الشغرات المتاحة.
- بالنسبة لـ $N$ فترة، الثلاثة التي يتوقعها المنهج هي: القسمة المتبقية (modulo)،
address ← key MOD N؛ طي المفتاح (folding)، قسّم المفتاح إلى أجزاء، اجمعها، ثم خذ باقي القسمة على $N$؛ تشفير السلاسل النصية (string hash)، اجمع رموز الأحرف، ثم خذ باقي القسمة على $N$.
دالة التجزئة:
تربط دالة التجزئة المفتاح بعنوان، مما يتيح بحثاً مباشراً سريعاً للغاية.
ما الذي يجعل دالة التجزئة جيدة؟ حدد كل الخيارات الصحيحة.
سريع، حتمي وموزع بالتساوي. لا يوجد تجانس واقعي يتجنب التصادم تمامًا، ولهذا يتضمن كل تصميم استراتيجية حل.
مثال محلول: تطبيق كل خوارزمية
- ملف يحتوي على 10 فترة مرقمة من 0 إلى 9. أين سيذهب المفتاح 4517؟
- القسمة المتبقية: $4517 \bmod 10 = 7$، إذن الفترة 7.
- الطي أزواجاً: $45 + 17 = 62$، ثم $62 \bmod 10 = 2$، إذن الفترة 2.
- وماذا عن المفتاح "CAB" باستخدام تشفير السلاسل النصية؟ $67 + 65 + 66 = 198$، ثم $198 \bmod 10 = 8$، إذن الفترة 8.
- اعرض العمليات الحسابية. العلامة تُمنح للحساب وليس رقم الفترة وحده.
باستخدام دالة التجانس address ← key MOD N باستخدام المعامل مع المقياس (modulo hash) حيث key = 27 و N = 10، ما العنوان الناتج؟
27 MOD 10 = 7 (الباقي عند قسمة 27 على 10).
جدول يحتوي على 10 خانات. باستخدام طي الأزواج على المفتاح 4517 (جمع 45 و 17، ثم MOD 10)، إلى أي خانة سيذهب؟
45 + 17 = 62، و 62 MOD 10 = 2. نفس المفتاح تحت دالة التجانس بالمقياس سيذهب إلى الخانة 7 بدلاً من ذلك.
التصادمات
- يحدث التصادم عندما يُشفّر مفتاحان مختلفان إلى نفس العنوان. مع أي دالة تشفير وأي ملف واقعي، التصادمات أمر حتمي، لذا فإن استراتيجية التعامل معها جزء من التصميم وليست تفكيراً لاحقاً.
- الفحص الخطي (Linear probing) يضع السجل في الفترة الحرة التالية، مع العودة للبداية عند نهاية الجدول. هو بسيط، لكن السجلات تتجمع: يزداد التكتل ويأخذ كل مفتاح يصل إليه وقتاً أطول.
- الربط (Chaining) يجعل كل فترة رأساً لـ قائمة مرتبطة بكل السجلات التي شُفرَت هناك. لا يوجد تجمع، لكنه يتطلب ذاكرة إضافية للروابط ومشي قصير عبر القائمة.
- إعادة التشفير (Rehashing) تطبق دالة تشفير ثانية لإيجاد فترة أخرى، مما يوزع المفاتيح بشكل أفضل على حساب زيادة الحسابات.
يحدث تصادم عندما:
تصوّر مفتاحين يشاركان في نفس الخانة هو تصادم؛ ويجب حله عن طريق التنقيب أو السلاسل أو إعادة التجانس.
طابق كل فكرة لمعالجة التصادم بما تقوم به.
يتم حل التصادمات عبر السلاسل أو التنقيب؛ والحفاظ على معامل تحميل منخفض يحافظ على عمليات البحث قريبة من O(1).
البحث والإدراج
- للإدراج: شفر المفتاح. إذا كانت الفترة فارغة، اكتب السجل هناك. وإذا لم تكن كذلك، اتبع استراتيجية الحل: الفترة الحرة التالية للفحص الخطي، أو بداية قائمة تلك الفترة للربط.
- للبحث: شفر المفتاح واقرأ تلك الفترة. إذا تطابق المفتاح المخزن، تم العثور على السجل. وإذا لم يتطابق، اتبع نفس الاستراتيجية، حتى تتطابق المفاتيح أو تثبت فترة فارغة أن السجل غير موجود في الملف.
- كلا العمليتين تستخدمان نفس الاستراتيجية. لو توقف البحث عند أول عدم تطابق، لفوت كل سجل طُرد بسبب تصادم سابق.
مثال محلول: تتبع تصادم
- جدول مكون من 10 فترات يستخدم
key MOD 10مع الفحص الخطي. أدخل 23، 33، 43 بالترتيب، ثم ابحث عن 43. - 23 يشفر إلى 3؛ الفترة 3 فارغة، فتدخلها. 33 يشفر إلى 3؛ الفترة 3 مشغولة بـ 23، فالفحص الخطي يضعه في الفترة 4. 43 يشفر إلى 3؛ الفترتان 3 و4 مشغولتان، فتدخل الفترة 5.
- البحث عن 43: شفر إلى 3، اقرأ الفترة 3، المفتاح هو 23، ليس تطابقاً، فاستمر في الفحص؛ الفترة 4 تحتوي على 33، ليس تطابقاً؛ الفترة 5 تحتوي على 43، تم العثور عليه بعد ثلاث قراءات.
- هذا التتابع المتزايد المكون من ثلاثة هو التجمع الذي يسببه الفحص الخطي.
اجزه كل مفتاح مباشرة إلى دلو
تحوّل دالة التجزئة المفتاح إلى رقم دلو، لتنتقل مباشرة إلى السجل بدلاً من البحث. عندما يسقط مفتاحان في نفس الدلو، يكون ذلك اصطداماً — يرتبطان بسلسلة داخل ذلك الدلو.
عند البحث في جدول تجانس، إذا لم يكن السجل موجودًا في الملف بمجرد قراءة أول خانة تحتوي على مفتاح مختلف.
قد يكون السجل قد تم إزاحته بسبب تصادم. يتبع البحث نفس استراتيجية الحل حتى يتم العثور على تطابق أو خانة فارغة.
معامل التحميل
- معامل التحميل هو عدد السجلات مقسوماً على عدد الفترات. إنه الرقم الوحيد الذي يتنبأ بكفاءة أداء الجدول.
- تحت حوالي 70% يكون متوسط الاستعلام قريباً من قراءة واحدة. فوقها، تمتد تسلسلات الفحص بشدة وتتدهور الأداء نحو البحث الخطي.
- الحل هو تكبير الجدول وإعادة تشفير كل سجل فيه، ولهذا السبب يُصمم جدول التشفير بناءً على البيانات التي سيحملها مستقبلاً، وليس ما يحمله اليوم.
جدول به 10 فترة يستخدم مفتاح MOD 10 مع المسح الخطي. بعد إدراج 23، 33 و43 بالترتيب، أي فترة تحتوي على 43؟
جميعها تُشفّر إلى 3. يأخذ 23 الخانة 3، و 33 يتم تنقيبه إلى 4، و 43 إلى 5. ثلاثة مفاتيح متتالية هي بالضبط ما يسببه التنقيب الخطي من تكتلات.
علامات ضائعة
- التصادم هو مفتاحان، عنوان واحد. ليس خطأً ولا سجلاً مفقوداً؛ بل هو الحالة الطبيعية التي تعالجها الاستراتيجية.
- يجب أن يتبع البحث نفس استراتيجية الحل الخاصة بالإدراج، ويتوقف فقط عند التطابق أو عند فترة فارغة.
- الفحص الخطي يسبب التجمع؛ الربط يكلف ذاكرة. قدم المقايضة، لا الآلية فحسب.
- معامل التحميل هو السجلات مقسومة على الفترات، والحد الأقصى حوالي 70%، وليس 100%.
للحفاظ على سرعات بحث التجانس، يجب إبقاء معامل التحميل (عدد السجلات ÷ عدد الخانات):
معامل التحميل الأقل يعني تصادمات أقل، لذا تبقى عمليات البحث قريبة من O(1).
لقد فهمت الأمر
- دالة التشفير تحول المفتاح إلى عنوان: سريعة، حتمية، موزعة بالتساوي؛ القسمة المتبقية، الطي، وتشفير السلاسل النصية هم الثلاثة المطلوب معرفتهم
- التصادم هو مفتاحان يشفران إلى عنوان واحد، يتم حله بـ الفحص الخطي (الفترة الحرة التالية، التجمع)، أو الربط (قائمة مرتبطة لكل فترة، ذاكرة أكثر) أو إعادة التشفير
- الإدراج والبحث يتبعان نفس الاستراتيجية؛ ينتهي البحث بالتطابق أو فترة فارغة
- احتفظ بـ معامل التحميل، السجلات مقسومة على الفترات، أقل من حوالي 70% لاستعلامات بقراءة واحدة تقريباً