جدول التجزئة في بنية البيانات: Python مثال

ما هو التجزئة؟

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

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

ما هو جدول التجزئة؟

A جدول التجزئة عبارة عن بنية بيانات تقوم بتخزين القيم باستخدام زوج من المفاتيح والقيم. يتم تعيين مفتاح فريد لكل قيمة يتم إنشاؤه باستخدام وظيفة التجزئة.

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

وظائف التجزئة

على سبيل المثال، إذا أردنا تخزين سجلات الموظفين، ويتم تعريف كل موظف بشكل فريد باستخدام رقم الموظف.

يمكننا استخدام رقم الموظف كمفتاح وتعيين بيانات الموظف كقيمة.

سيتطلب النهج المذكور أعلاه مساحة حرة إضافية بترتيب (م * ن²) حيث المتغير m هو حجم مجموعة، والمتغير n هو عدد أرقام رقم الموظف. يقدم هذا الأسلوب مشكلة مساحة التخزين.

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

فيما يلي مثال لدالة تجزئة بسيطة

h(k) = k1 % m

هنا،

• h(k) هي دالة التجزئة التي تقبل المعلمة k. المعلمة k هي القيمة التي نريد حساب المفتاح لها.
• k₁ %m هي الخوارزمية المستخدمة في دالة التجزئة حيث k1 هي القيمة التي نريد تخزينها، وm هو حجم القائمة. نستخدم عامل المعامل لحساب المفتاح.

مثال

لنفترض أن لدينا قائمة بحجم ثابت 3 والقيم التالية

[1,2,3]

يمكننا استخدام الصيغة أعلاه لحساب المواضع التي يجب أن تشغلها كل قيمة.

الصورة التالية توضح الفهارس المتوفرة في جدول التجزئة الخاص بنا.

الخطوة 1) احسب الموضع الذي ستشغله القيمة الأولى هكذا

ح(1) = 1% 3

= 1

القيمة 1 سيحتل الفضاء على مؤشر 1

الخطوة 2) احسب الموضع الذي ستشغله القيمة الثانية

ح(2) = 2% 3

= 2

القيمة 2 سيحتل الفضاء على مؤشر 2

الخطوة 3) احسب الموضع الذي ستشغله القيمة الثالثة.

ح(3) = 3% 3

= 0

القيمة 3 سيحتل الفضاء على مؤشر 0

النتيجة النهائية

سيكون جدول التجزئة المملوء لدينا الآن على النحو التالي.

صفات وظيفة التجزئة الجيدة

يجب أن تتمتع دالة التجزئة الجيدة بالصفات التالية.

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

تصادم

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

لنلقي نظرة على مثال.

افترض أن لدينا القائمة التالية من القيم

[3,2,9,11,7]

لنفترض أن حجم جدول التجزئة هو 7، وسوف نستخدم الصيغة (k₁ % m) حيث m هو حجم جدول التجزئة.

يوضح الجدول التالي قيم التجزئة التي سيتم إنشاؤها.

كما نرى من النتائج المذكورة أعلاه، فإن القيمتين 2 و9 لهما نفس قيمة التجزئة، ولا يمكننا تخزين أكثر من قيمة واحدة في كل موضع.

يمكن حل المشكلة المذكورة إما باستخدام التسلسل أو الاستكشاف. تناقش الأقسام التالية التسلسل والاستكشاف بالتفصيل.

تسلسل

التسلسل هو أسلوب يستخدم لحل مشكلة التصادم باستخدام قوائم مرتبطة تحتوي كل منها على فهارس فريدة.

الصورة التالية توضح كيف تبدو القائمة المتسلسلة

يشغل كل من 2 و9 نفس الفهرس، لكن يتم تخزينهما كقوائم مرتبطة. كل قائمة لها معرف فريد.

فوائد القوائم المتسلسلة

وفيما يلي فوائد القوائم المتسلسلة:

• تتمتع القوائم المتسلسلة بأداء أفضل عند إدراج البيانات لأن ترتيب الإدراج هو O(1).
• ليس من الضروري تغيير حجم جدول التجزئة الذي يستخدم قائمة متسلسلة.
• يمكنه بسهولة استيعاب عدد كبير من القيم طالما توفرت مساحة خالية.

جس

التقنية الأخرى المستخدمة لحل التصادم هي التحقيق. عند استخدام طريقة الفحص، في حالة حدوث تصادم، يمكننا ببساطة المضي قدمًا والعثور على فتحة فارغة لتخزين القيمة الخاصة بنا.

وفيما يلي طرق التحقيق:

باستخدام المثال أعلاه، سيظهر جدول التجزئة بعد استخدام الفحص كما يلي:

عمليات جدول التجزئة

هنا، هي Operaالعناصر التي تدعمها جداول التجزئة:

• إدخال - هذه Operaيتم استخدام tion لإضافة عنصر إلى جدول التجزئة
• البحث - هذه Operaيتم استخدام tion للبحث عن العناصر في جدول التجزئة باستخدام المفتاح
• حذف - هذه Operaيتم استخدام tion لحذف العناصر من جدول التجزئة

عملية إدخال البيانات

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

البحث عن عملية البيانات

تُستخدم عملية البحث للبحث عن القيم في جدول التجزئة باستخدام رقم الفهرس. تُرجع عملية البحث القيمة المرتبطة برقم فهرس البحث. على سبيل المثال، إذا قمنا بتخزين القيمة 6 عند الفهرس 2، فإن عملية البحث برقم الفهرس 2 ستعيد القيمة 6.

عملية حذف البيانات

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

تنفيذ جدول التجزئة مع Python مثال

دعونا نلقي نظرة على مثال بسيط يحسب قيمة التجزئة للمفتاح

def hash_key( key, m):
    return key % m


m = 7

print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')

جدول تجزئة Code تفسير

هنا،

1. يحدد دالة hash_key التي تقبل مفتاح المعلمات وm.
2. يستخدم عملية معامل بسيطة لتحديد قيمة التجزئة
3. يحدد المتغير m الذي تمت تهيئته إلى القيمة 7. هذا هو حجم جدول التجزئة الخاص بنا
4. حساب وطباعة قيمة التجزئة 3
5. حساب وطباعة قيمة التجزئة 2
6. حساب وطباعة قيمة التجزئة 9
7. حساب وطباعة قيمة التجزئة 11
8. حساب وطباعة قيمة التجزئة 7

يؤدي تنفيذ الكود أعلاه إلى النتائج التالية.

The hash value for 3 is 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

Python مثال القاموس

Python يأتي مع نوع بيانات مدمج يسمى القاموس. القاموس هو مثال لجدول التجزئة. يقوم بتخزين القيم باستخدام زوج من المفاتيح والقيم. يتم إنشاء قيم التجزئة لنا تلقائيًا، ويتم حل أي تصادمات لنا في الخلفية.

يوضح المثال التالي كيفية استخدام نوع بيانات القاموس في بيثون 3

employee = {
    'name': 'John Doe',
    'age': 36,
    'position': 'Business Manager.'
}

print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()

print (employee)

هنا،

1. تعريف موظف متغير القاموس. يتم استخدام اسم المفتاح لتخزين القيمة John Doe، ويخزن العمر 36، ويخزن المنصب القيمة Business Manager.
2. يسترد قيمة اسم المفتاح ويطبعه في الجهاز
3. يقوم بتحديث قيمة موضع المفتاح إلى قيمة مهندس البرمجيات
4. يطبع قيم اسم المفاتيح وموضعها
5. يحذف جميع القيم المخزنة في متغير القاموس الخاص بنا
6. يطبع قيمة الموظف

يؤدي تشغيل الكود أعلاه إلى النتائج التالية.

The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}

تحليل التعقيد

تتمتع جداول التجزئة بتعقيد زمني متوسط ​​يبلغ O (1) في أفضل السيناريوهات. أما أسوأ السيناريوهات فهي O(n). ويحدث أسوأ سيناريو عندما تولد العديد من القيم نفس مفتاح التجزئة، ويتعين علينا حل التصادم عن طريق الفحص.

تطبيقات العالم الحقيقي

في العالم الحقيقي، يتم استخدام جداول التجزئة لتخزين البيانات

• قواعد بيانات
• صفائف ترابطية
• أطقم / مجموعات
• الذاكرة المؤقتة

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

فيما يلي إيجابيات/فوائد استخدام جداول التجزئة:

• تتمتع جداول التجزئة بأداء عالٍ عند البحث عن البيانات وإدراج وحذف القيم الموجودة.
• تظل التعقيدات الزمنية لجداول التجزئة ثابتة بغض النظر عن عدد العناصر الموجودة في الجدول.
• إنها تؤدي أداءً جيدًا للغاية حتى عند العمل مع مجموعات البيانات الكبيرة.

عيوب جداول التجزئة

فيما يلي سلبيات استخدام جداول التجزئة:

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

الأسئلة الشائعة