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

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

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

بالنظر إلى التسلسل "qrj" و "aty" و "qur" و "dim" و "ofu" و "gcl" و "rhv" و "clq" و "ecd" و "qsu" من السلاسل النصية المكونة من ثلاثة أحرف عشوائيًا، سيتم إنشاء الجدول التالي (باستخدام خوارزمية التجزئة One-at-a-Time لبوب جينكينز ) بحجم 10:

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

أحد حلول هذه المشكلات هو التجزئة المدمجة. تستخدم التجزئة المدمجة تقنية مشابهة للتجزئة المنفصلة، ​​ولكن بدلاً من تخصيص عُقد جديدة للقائمة المرتبطة، تُستخدم خانات في الجدول نفسه. تُعتبر أول خانة فارغة في الجدول عند حدوث تصادم هي خانة التصادم. عند حدوث تصادم في أي مكان في الجدول، يُوضع العنصر في خانة التصادم، ويُنشأ رابط بين السلسلة وخانة التصادم. من الممكن أن يتصادم عنصر مُضاف حديثًا مع عناصر ذات عنوان تجزئة مختلف، كما هو الحال في المثال الموضح في الصورة عند إدخال العنصر "clq". يُقال إن سلسلة "clq" "تتحد" مع سلسلة "qrj"، ومن هنا جاء اسم الخوارزمية. مع ذلك، فإن مدى الاندماج ضئيل مقارنةً بالتجميع الذي تُظهره العنونة المفتوحة. على سبيل المثال، عند حدوث الاندماج، يزداد طول السلسلة بمقدار 1 فقط، بينما في العنونة المفتوحة، قد تتحد تسلسلات البحث ذات الأطوال المختلفة.

من أهم التحسينات، للحد من تأثير التداخل، حصر نطاق عناوين دالة التجزئة في مجموعة فرعية من الجدول. على سبيل المثال، إذا كان حجم الجدول M، وعدد خاناته مرقمة من 0 إلى M - 1 ، فيمكننا حصر نطاق العناوين بحيث تُخصص دالة التجزئة عناوين لأول N خانة فقط في الجدول. أما الخانات المتبقية وعددها M - N ، والتي تُسمى "القبو" ، فتُستخدم حصريًا لتخزين العناصر المتداخلة أثناء الإدخال. ولا يحدث أي تداخل حتى يتم استنفاد القبو.

يعتمد الاختيار الأمثل لقيمة N بالنسبة إلى M على معامل التحميل (أو امتلاء) الطاولة. يُظهر تحليل دقيق أن القيمة N = 0.86 × M تُحقق أداءً شبه مثالي لمعظم معاملات التحميل. ^{[ 1 ] [ 2 ]}

توجد أيضًا طرق أخرى للإدخال تُحسّن وقت البحث. وقد طُوّرت خوارزميات حذف تحافظ على العشوائية، وبالتالي يظل تحليل متوسط ​​وقت البحث صحيحًا بعد عمليات الحذف. ^{[ 1 ]}

الإدخال في C :

/* htab هو جدول التجزئة،  وN هو حجم مساحة عناوين دالة التجزئة، و  M هو حجم الجدول بأكمله بما في ذلك القبو.  يتم تخصيص حاويات التصادم بترتيب تنازلي، بدءًا من الحاوية M-1. */int insert ( char key [] ) { unsigned h = hash ( key , strlen ( key ) ) % N ;إذا كان ( htab [ h ] == NULL ) { /* إنشاء سلسلة جديدة */ htab [ h ] = make_node ( key , NULL ); } else { struct node * it ; int cursor = M - 1 ;/* ابحث عن أول دلو فارغ */ while ( cursor >= 0 && htab [ cursor ] != NULL ) -- cursor ;/* الجدول ممتلئ، إنهاء العملية غير ناجح */ إذا كان ( المؤشر == -1 ) أرجع -1 ؛htab [ cursor ] = make_node ( key , NULL ); /* ابحث عن العقدة الأخيرة في السلسلة وأشر إليها */ it = htab [ h ];بينما ( it -> next != NULL ) it = it -> next ;it -> next = htab [ cursor ]; }return 0 ; }

إحدى فوائد هذه الاستراتيجية هي أنه يمكن استخدام خوارزمية البحث عن التسلسل المنفصل دون تغيير في جدول التجزئة المدمج.

البحث في لغة C:

char * find ( char key [] ) { unsigned h = hash ( key , strlen ( key ) ) % N ;إذا كان ( htab [ h ] != NULL ) { struct node * it ;/* ابحث في السلسلة عند الفهرس h */ for ( it = htab [ h ]; it != NULL ; it = it -> next ) { if ( strcmp ( key , it -> data ) == 0 ) return it -> data ; } }return NULL ; }

قد يكون الحذف صعباً. ^{[ 3 ] [ 4 ]}

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