التجزئة في بنية البيانات: الوظيفة ، الأساليب [مع أمثلة]

نشرت: 2021-05-02

جدول المحتويات

مقدمة

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

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

ستمنحك هذه المدونة فهمًا أعمق لطريقة التجزئة وجداول التجزئة والتحقيق الخطي باستخدام الأمثلة.

ما هو التجزئة في بنية البيانات؟

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

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

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

التجزئة في بنية البيانات هي عملية من خطوتين.

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

أمثلة على التجزئة في بنية البيانات

فيما يلي أمثلة واقعية للتجزئة في بنية البيانات -

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

الخروج: الفرز في بنية البيانات

دالة تجزئة

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

التجزئة = hashfunc (مفتاح)

الفهرس = التجزئة٪ array_size

يجب أن تفي وظيفة has بالمتطلبات التالية:

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

جدول تجزئة

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

كيف يعمل التجزئة في بنية البيانات؟

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

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

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

القيم هي: (3،21) (1،72) (40،36) (5،30) (11،44) (15،33) (18،12) (16،80) (38،99)

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

رقم سري مفتاح تجزئة فهرس المصفوفة
1 3 3٪ 30 = 3 3
2 1 1٪ 30 = 1 1
3 40 40٪ 30 = 10 10
4 5 5٪ 30 = 5 5
5 11 11٪ 30 = 11 11
6 15 15٪ 30 = 15 15
7 18 18٪ 30 = 18 18
8 16 16٪ 30 = 16 16
9 38 38٪ 30 = 8 8

اقرأ أيضًا: أنواع هياكل البيانات في بايثون

تقنيات دقة التصادم

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

السبر الخطي

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

مثال الفحص الخطي

تخيل أنه طُلب منك تخزين بعض العناصر داخل جدول تجزئة بحجم 30. تم فرز العناصر بالفعل في تنسيق زوج مفتاح-قيمة. القيم المعطاة هي: (3،21) (1،72) (63،36) (5،30) (11،44) (15،33) (18،12) (16،80) (46،99) .

التجزئة (n) هي الفهرس المحسوب باستخدام دالة التجزئة و T هو حجم الجدول. إذا كان فهرس الفتحة = (التجزئة (n)٪ T) ممتلئًا ، فإننا نبحث عن فهرس الفتحة التالي بإضافة 1 ((التجزئة (n) + 1)٪ T). إذا كانت (التجزئة (n) + 1)٪ T ممتلئة أيضًا ، فإننا نحاول (التجزئة (n) + 2)٪ T. إذا كانت (التجزئة (n) + 2)٪ T ممتلئة أيضًا ، فإننا نحاول (التجزئة (التجزئة ( ن) + 3)٪ T.

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

رقم سري مفتاح تجزئة فهرس المصفوفة فهرس المصفوفة بعد السبر الخطي
1 3 3٪ 30 = 3 3 3
2 1 1٪ 30 = 1 1 1
3 63 63٪ 30 = 3 3 4
4 5 5٪ 30 = 5 5 5
5 11 11٪ 30 = 11 11 11
6 15 15٪ 30 = 15 15 15
7 18 18٪ 30 = 18 18 18
8 16 16٪ 30 = 16 16 16
9 46 46٪ 30 = 8 16 17

تجزئة مزدوجة

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

صيغة تقنية التجزئة المزدوجة هي كما يلي:

(firstHash (key) + i * secondHash (key))٪ sizeOfTable

أين أنا قيمة الإزاحة. تستمر قيمة الإزاحة هذه في الزيادة حتى تعثر على فتحة فارغة.

على سبيل المثال ، لديك وظيفتان تجزئة: h1 و h2. يجب عليك تنفيذ الخطوات التالية للعثور على فتحة فارغة:

  1. تحقق مما إذا كانت التجزئة 1 (المفتاح) فارغة. إذا كانت الإجابة بنعم ، فقم بتخزين القيمة في هذه الفتحة.
  2. إذا لم يكن التجزئة 1 (مفتاح) فارغًا ، فابحث عن فتحة أخرى باستخدام التجزئة 2 (مفتاح).
  3. تحقق مما إذا كانت التجزئة 1 (مفتاح) + التجزئة 2 (مفتاح) فارغة. إذا كانت الإجابة بنعم ، فقم بتخزين القيمة في هذه الفتحة.
  4. استمر في زيادة العداد وكرر الأمر مع التجزئة 1 (مفتاح) + 2 هاش 2 (مفتاح) ، التجزئة 1 (مفتاح) + 3 هاش 2 (مفتاح) ، وهكذا ، حتى يجد فتحة فارغة.

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

تخيل أنك بحاجة إلى تخزين بعض العناصر داخل جدول تجزئة بحجم 20. القيم المعطاة هي: (16 ، 8 ، 63 ، 9 ، 27 ، 37 ، 48 ، 5 ، 69 ، 34 ، 1).

h1 (n) = n٪ 20

h2 (ن) = ن٪ 13

nh (n، i) = (h1 (n) + ih2 (n)) mod 20

ن ح (ن ، أنا) = (ح '(ن) + أنا 2 )٪ 20
16 أنا = 0 ، ح (ن ، 0) = 16
8 أنا = 0 ، ح (ن ، 0) = 8
63 أنا = 0 ، ح (ن ، 0) = 3
9 أنا = 0 ، ح (ن ، 0) = 9
27 أنا = 0 ، ح (ن ، 0) = 7
37 أنا = 0 ، ح (ن ، 0) = 17
48 أنا = 0 ، ح (ن ، 0) = 8

أنا = 0 ، ح (ن ، 1) = 9

أنا = 0 ، ح (ن ، 2) = 12

5 أنا = 0 ، ح (ن ، 0) = 5
69 أنا = 0 ، ح (ن ، 0) = 9

أنا = 0 ، ح (ن ، 1) = 10

34 أنا = 0 ، ح (ن ، 0) = 14
1 أنا = 0 ، ح (ن ، 0) = 1
تعلم دورات تطوير البرمجيات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.

خاتمة

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

يمكنك تجربة المثال لتقوية معرفتك بهيكل البيانات. إذا كنت مهتمًا بمعرفة المزيد عن بنية البيانات ، فراجع برنامج upGrad Executive PG في دورة Full Stack Development . تم تصميم هذه الدورة للمهنيين العاملين وتقدم تدريبًا صارمًا وتوظيفًا مع أفضل الشركات.

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

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

ما هي تطبيقات وظائف التجزئة؟

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

ما هي تقنيات دقة التصادم في التجزئة؟

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