جدول التقطيع، في علوم الحاسب هو عبارة عن بنية معطيات تربط مفاتيح بقيم. كما تدعم هذه البنية العمليات المعجميّة (البحث, الإضافة و الحذف) بفعاليّة عالية, حيث بالاستطاعة القيام بكلِ من هذه العمليات باستعمال هذه البنية في زمن ثابت (O(1. تقوم هذه البنية بتحويل المفتاح إلى قيمة عددية عادةً بوساطة تابع تقطيع.
العمليات الأساسية
يقوم جدول التقطيع بتحويل المفتاح إلى قيمة عددية باستخدام تابع تقطيع, هذه القيمة العددية تحدد مكان العنصر الحامل للمفتاح المقابل لها, تختلف جودة تابع التقطيع باختلاف التطبيق الذي يستخدم الجدول فيه و باختلاف تابع التقطيع.
حيث ان بعض العمليات المعتادة على توابع التقطيع تتضمن الإدخال, الحذف و البحث, تنفذ كل هذه العملبات في وقت ثابت (بالكلفة), مما يجعل استخدام هذه الجداول عملية فعالة جداً.
معامل الحمل
هي واحدة من اهم الخواص الضرورية لجدول تقطيع ما هو نسبة امتلاء هذا الجدول, و هو نسبة عدد العناصر الموجودة في الجدول(n) إلى مساحة الجدول الكليّة (m).
و منه, يتضح تسمية النسبة (a=n/m) بمعامل الحمل.
معظم جداول التقطيع تربط الأداء الجيد ببقاء
عامل الحمل في مجال معين.
حل التصادمات
بما أن الهدف من التقطيع هو إيجاد قيمة وحيدة لكل مفتاح, فعندما يوجد تابع التقطيع القيمة ذاتها لأكثر من مفتاح فيجب إيجاد مكان بديل للمفتاح الجديد, عملية إيجاد مكان جديد تعرف ب: حل التصادمات, إن حل التصادمات يجب أن يكون بخوارزمية محددة, أي أن يضمن أن البحث المستقبلي عن القيمة سيرد النتيجة الصحيحة.
المراجع
areq.net
التصانيف
علم الحاسوب العلوم التطبيقية تقنية المعلومات