هيكلة البيانات بواسطة جدول التجزئة Hash Table

مفهوم جدول التجزئة Hash Table:

تعد من أنواع هياكل البيانات المهمة والسريعة وسهلة التطبيق، حيث يمثل البيانات على شكل أزواج (مفتاح وقيمة)، يتم تعيين كل مفتاح (key) لقيمة (value) في جدول التجزئة، حيث تُستخدم المفاتيح لفهرسة القيم/ البيانات، وتتم معالجة المفاتيح لإنتاج فهرس (index) جديد ليتم تعيينه للعنصر المطلوب، هذه العملية تسمى التجزئة (hashing).

افرض أن لديك (object) وتريد تعيين مفتاح له لتسهيل البحث، ولتخزين زوج (المفتاح/ القيمة)، يمكنك استخدام المصفوفة البسيطة لهيكلة البيانات حيث أن المفاتيح هي (integers) ويمكن استخدام المؤشر (index) لتخزين القيم بشكل مباشر، مع ذلك، في الحالات التي تكون فيها المفاتيح كبيرة ولا يمكن استخدامها كمؤشر بشكل مباشر، يجب استخدام التجزئة (hashing) لهيكلة البيانات.

في التجزئة (hashing)، يتم تحويل المفاتيح الكبيرة إلى مفاتيح صغيرة باستخدام دالة التجزئة، ومن ثم يتم تخزين القيم في جدول التجزئة، وفكرة التجزئة تقوم على توزيع المدخلات (زوج من المفتاح والقيمة) بشكل موحد عبر مصفوفة، ويتم تعيين مفتاح لكل عنصر (مفتاح محوّل). باستخدام هذا المفتاح، يمكنك الوصول إلى العنصر في وقت هو “O(1)”، باستخدام المفتاح أيضاً، فإن الخوارزمية (دالة التجزئة) تقوم بحساب فهرس (index) والذي بدوره يشير لمكان يمكنك الاطلاع على قيمة أو إدراج قيمة.

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

تنفيذ جدول التجزئة:

حيث يتم تنفيذ التجزئة على خطوتين:

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

• يتم تخزين العنصر في جدول التجزئة، حيث يمكن استرجاعه بسرعة باستخدام مفتاح مجزأ (hashed).

دالة التجزئة Hash Function:

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

سهلة الحساب: يجب أن تكون سهلة الحساب، ويجب ألا تصبح خوارزمية في حد ذاتها.

التوزيع الموحد: يجب أن توفر الدالة توزيعًا موحدًا عبر جدول التجزئة، ويجب ألا يؤدي إلى تكتل.

تصادمات أقل: تحدث التصادمات عند تعيين أزواج من العناصر إلى نفس قيمة التجزئة. (بغض النظر عن مدى جودة وظيفة التجزئة، لا بد أن تحدث التصادمات) للحفاظ على أداء جدول التجزئة، من المهم إدارة التصادمات من خلال تقنيات مختلفة لتحليل التصادم.

ما مدى الحاجة إلى دالة تجزئة سليمة؟

دعونا نفهم الحاجة إلى دالة تجزئة سليمة، افرض أن عليك تخزين هذه الـ (strings) في جدول التجزئة باستخدام تقنية التجزئة {“abcdef” ، “bcdefa” ، “cdefab” ، “defabc”}. لحساب الفهرس لتخزين ال (strings)، استخدم دالة التجزئة التي تنص على ما يلي: سيكون الفهرس لـ (string) معين مساويًا لمجموع قيم (ASCII) للأحرف في الكلمة، ثم يؤخذ باقي قسمة المجموع على (599) باستخدام ال (modulo %).

نظرًا لأن (599) عدد أولي، فإنه سيقلل من إمكانية فهرسة ال (strings) التي تُحتمل فيها التصادمات، لكن مع ذلك سيحدث هنا تصادم إذ أن قيم (ASCII) لـ (a و b و c و d و e و f)، هي (97 و 98 و 99 و 100 و 101 و 102) على التوالي، ونظرًا لأن جميع الـ (strings) في المثال تحتوي على نفس الأحرف مع تبديلات مختلفة، فسيكون المجموع (599)، وستحسب دالة التجزئة نفس الفهرس (index) لجميع الـ (strings)، أي أنه سيتم تخزين جميع الـ (strings) على نفس الفهرس في جدول التجزئة، نظرًا لأن فهرس جميع الـ (strings) هو نفسه.

سيتم إنشاء قائمة على هذا الفهرس (index) وإدراج جميع الـ (strings) في تلك القائمة،
هنا، وللوصول إلى (string) محدد، سيستغرق الأمر وقت مقداره “O(n)”، حيث يمثل (n) عدد الـ (strings)، يوضح هذا أن دالة التجزئة ليست دالة تجزئة سليمة.

تطبيقات على جدول التجزئة Hash Table:

• المصفوفات الترابطية (Associative arrays): تُستخدم جداول التجزئة بشكل شائع لتنفيذ العديد من أنواع الجداول في الذاكرة، ويتم استخدامها لتنفيذ المصفوفات الترابطية (المصفوفات التي تكون مؤشراتها سلاسل عشوائية أو “objects” أخرى معقدة).

• فهرسة قاعدة البيانات: يمكن أيضًا استخدام جداول التجزئة كتركيبات بيانات (disk-based)، ومؤشرات قاعدة بيانات.

• ذاكرات التخزين المؤقت (Caches): يمكن استخدام جداول التجزئة لتنفيذ (implement) ذاكرات التخزين المؤقت، على سبيل المثال، جداول البيانات المساعدة التي تُستخدم لتسريع الوصول إلى البيانات، والتي يتم تخزينها بشكل أساسي في وسائط أبطأ.

• تمثيل الـ (object): تستخدم العديد من اللغات الديناميكية، مثل (Perl و Python و JavaScript و Ruby)، جداول التجزئة لتنفيذ الـ (objects).

• تُستخدم دوال التجزئة في العديد من الخوارزميات لجعل الحوسبة أسرع.