دالة تجزئة
سنتحدث في هذا القسم عن دالة التجزئة التي تساعد على تنفيذ كود التجزئة للمفتاح المرتبط بعنصر البيانات في بنية البيانات كما هو مذكور فيما يلي:
Int hashItem ( كثافة العمليات مفتاح ){
يعود مفتاح % حجم الجدول ;
}
تسمى عملية تنفيذ فهرس المصفوفة بالتجزئة. في بعض الأحيان، يتم تنفيذ نفس النوع من التعليمات البرمجية لإنشاء نفس الفهرس باستخدام نفس المفاتيح التي تسمى الاصطدامات والتي يتم التعامل معها من خلال تسلسل مختلف (إنشاء قائمة مرتبطة) وتنفيذ استراتيجيات العنونة المفتوحة.
عمل جدول التجزئة في C++
يتم الاحتفاظ بالمؤشرات إلى القيم الحقيقية في جدول التجزئة. يستخدم مفتاحًا للبحث عن فهرس المصفوفة حيث يجب تخزين القيم مقابل المفاتيح في الموقع المطلوب في المصفوفة. أخذنا جدول التجزئة بحجم 10 كما هو مذكور في ما يلي:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
دعونا نأخذ بشكل عشوائي أي بيانات مقابل مفاتيح مختلفة ونخزن هذه المفاتيح في جدول التجزئة عن طريق حساب الفهرس فقط. لذلك، يتم تخزين البيانات مقابل المفاتيح الموجودة في الفهرس المحسوب بمساعدة دالة التجزئة. لنفترض أننا أخذنا البيانات = {14,25,42,55,63,84} والمفاتيح =[ 15,9,5,25,66,75 ].
احسب فهرس هذه البيانات باستخدام دالة التجزئة. قيمة الفهرس مذكورة في ما يلي:
| مفتاح | خمسة عشر | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| حساب الفهرس | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| بيانات | 14 | 25 | 42 | 55 | 63 | 84 |
بعد إنشاء فهرس مصفوفة، ضع البيانات مقابل المفتاح الموجود على الفهرس الدقيق لمصفوفة معينة كما هو موضح سابقًا.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
بعد ذلك، يمكننا أن نرى أن التصادم يحدث إذا كان هناك مفتاحان أو أكثر لهما نفس رمز التجزئة مما يؤدي إلى نفس فهرس العناصر الموجودة في المصفوفة. لدينا حل واحد لتجنب فرص الاصطدام: اختيار طريقة تجزئة جيدة وتنفيذ الاستراتيجيات الدقيقة.
الآن، دعونا نناقش تقنيات التنفيذ المختلفة بمساعدة الأمثلة المناسبة.
مثال: إضافة بيانات في جدول التجزئة باستخدام تقنية التجزئة المفتوحة
في هذا المثال، نستخدم تقنية تنفيذ مثل Open Hashing لتجنب الاصطدام في جدول التجزئة. في التجزئة أو التسلسل المفتوح، نقوم بإنشاء قائمة مرتبطة لتسلسل قيم جدول التجزئة. تم إرفاق مقتطف الكود الخاص بهذا المثال فيما يلي والذي يصف تقنية التجزئة المفتوحة:
#تشمل#تشمل <القائمة>
فصل HashTable {
خاص :
ثابتة مقدار ثابت كثافة العمليات حجم الجدول = 10 ;
الأمراض المنقولة جنسيا :: قائمة < كثافة العمليات > tableHas [ حجم الجدول ] ;
كثافة العمليات hashFunc ( كثافة العمليات مفتاح ) {
يعود مفتاح % حجم الجدول ;
}
عام :
فارغ إدراج ( كثافة العمليات مفتاح ) {
كثافة العمليات فِهرِس = hashFunc ( مفتاح ) ;
tableHas [ فِهرِس ] . إدفع إلى الخلف ( مفتاح ) ;
}
فارغ viewTable ( ) {
ل ( كثافة العمليات أنا = 0 ; أنا < حجم الجدول ; ++ أنا ) {
الأمراض المنقولة جنسيا :: cout << '[' << أنا << ']' ;
ل ( آلي هو - هي = tableHas [ أنا ] . يبدأ ( ) ; هو - هي ! = tableHas [ أنا ] . نهاية ( ) ; ++ هو - هي ) {
الأمراض المنقولة جنسيا :: cout << ' -> ' << * هو - هي ;
}
الأمراض المنقولة جنسيا :: cout << الأمراض المنقولة جنسيا :: endl ;
}
}
} ;
كثافة العمليات رئيسي ( ) {
HashTable hasTable ;
hasTable. إدراج ( خمسة عشر ) ;
hasTable. إدراج ( 33 ) ;
hasTable. إدراج ( 23 ) ;
hasTable. إدراج ( 65 ) ;
hasTable. إدراج ( 3 ) ;
hasTable. viewTable ( ) ;
يعود 0 ;
}
هذا مثال مثير للاهتمام للغاية: قمنا ببناء قائمة مرتبطة وإدراج البيانات في جدول التجزئة. أولاً، نقوم بتعريف المكتبات في بداية البرنامج. ال < قائمة > يتم استخدام المكتبة لتنفيذ القائمة المرتبطة. بعد ذلك، نقوم ببناء فئة باسم 'HashTable' وإنشاء سمات الفئة الخاصة مثل حجم الجدول ومصفوفة الجدول باستخدام الكلمة الأساسية 'خاص:'. تذكر أن السمات الخاصة غير قابلة للاستخدام خارج الفصل. هنا، نأخذ حجم الجدول على أنه '10'. نقوم بتهيئة طريقة التجزئة باستخدام هذا ونحسب فهرس جدول التجزئة. في دالة التجزئة، نقوم بتمرير مفتاح وحجم جدول التجزئة.
نحن نبني بعض الوظائف المطلوبة ونجعل هذه الوظائف عامة في الفصل. تذكر أن الوظائف العامة قابلة للاستخدام خارج الفصل في أي مكان. نستخدم الكلمة الأساسية 'عام:' لبدء الجزء العام من الفصل الدراسي . نظرًا لأننا نريد إضافة عناصر جديدة إلى جدول التجزئة، فإننا نقوم بإنشاء وظيفة تسمى 'InsertHash' باستخدام مفتاح كوسيطة للوظيفة. في الدالة 'insert'، نقوم بتهيئة متغير الفهرس. نقوم بتمرير دالة التجزئة إلى متغير الفهرس. بعد ذلك، قم بتمرير متغير الفهرس إلى جدول القائمة المرتبطة[]باستخدام طريقة 'الدفع' لإدراج عنصر في الجدول.
بعد ذلك، قمنا ببناء وظيفة “viewHashTab” لعرض جدول التجزئة لرؤية البيانات المدخلة حديثًا. في هذه الوظيفة، نأخذ حلقة 'for' التي تبحث عن القيم حتى نهاية جدول التجزئة. تأكد من تخزين القيم في نفس الفهرس الذي تم تطويره باستخدام دالة التجزئة. في الحلقة، نقوم بتمرير القيم في الفهرس الخاص بها وننهي الفصل هنا. في الوظيفة 'الرئيسية'، نأخذ كائن فئة يسمى 'hasTable'. بمساعدة كائن الفئة هذا، يمكننا الوصول إلى طريقة الإدراج عن طريق تمرير المفتاح في الطريقة. يتم حساب المفتاح الذي مررناه في الدالة 'الرئيسية' في الدالة 'إدراج' التي تُرجع موضع الفهرس في جدول التجزئة. قمنا بعرض جدول التجزئة عن طريق استدعاء وظيفة 'العرض' بمساعدة كائن 'الفئة'.
يتم إرفاق إخراج هذا الكود في ما يلي:
كما نرى، تم إنشاء جدول التجزئة بنجاح باستخدام القائمة المرتبطة في C++. يتم استخدام التسلسل المفتوح لتجنب تصادم نفس المؤشر.
خاتمة
في النهاية، خلصنا إلى أن جدول التجزئة هو الأسلوب الأكثر ظهورًا لتخزين المفاتيح والحصول عليها بأزواج القيمة للتعامل مع كميات هائلة من البيانات بكفاءة. فرص الاصطدام عالية جدًا في جدول التجزئة، مما يؤدي إلى تدمير البيانات وتخزينها. يمكننا التغلب على هذا الاصطدام باستخدام تقنيات مختلفة لإدارة جدول التجزئة. من خلال تطوير جدول التجزئة في C++، يمكن للمطورين زيادة الأداء باستخدام أفضل تقنية مناسبة لتخزين البيانات في جدول التجزئة. نأمل أن تكون هذه المقالة مفيدة لفهم جدول التجزئة.