ما هو التجزئة؟ كيف تعمل أكواد التجزئة - مع الأمثلة

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

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

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

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

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

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

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

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

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

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

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

  • إدراج (مفتاح ، قيمة)
  • احصل على مفتاح)
  • حذف (مفتاح)

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

لنفترض أننا نريد تخزين البيانات في جدول على الخريطة.

ودعنا نفترض أن دالة التجزئة لدينا هي ببساطة أخذ طول السلسلة.

من أجل التبسيط ، سيكون لدينا صفيفتان: واحدة لمفاتيحنا وواحدة للقيم.

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

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

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

نحن نضيع القليل من المساحة لأنه ، على سبيل المثال ، لا توجد مفاتيح من حرف واحد في بياناتنا ، ولا مفاتيح بين 8 و 10 أحرف.

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

ولكن ، ماذا نفعل إذا كانت مجموعة البيانات الخاصة بنا تحتوي على سلسلة بها أكثر من 11 حرفًا؟

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

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

التعامل مع الاصطدام

يتم استخدام طريقتين أساسيتين للتعامل مع الاصطدامات.

  1. تسلسل منفصل
  2. افتح العنونة

تسلسل منفصل

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

للعثور على عنصر ما ، نذهب أولاً إلى الجرافة ثم نقارن المفاتيح. هذه طريقة شائعة ، وإذا تم استخدام قائمة الروابط ، فلن تملأ التجزئة مطلقًا. التكلفة get(k)في المتوسط O(n)حيث n هو عدد المفاتيح في الحاوية ، إجمالي عدد المفاتيح هو N.

تكمن مشكلة التسلسل المنفصل في أن بنية البيانات يمكن أن تنمو بلا حدود.

افتح العنونة

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

طرق العنونة المفتوحة

  • [السبر الخطي
  • سبر من الدرجة الثانية
  • تجزئة مزدوجة

كيفية استخدام التجزئة في التعليمات البرمجية الخاصة بك.

بايثون

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:صاروخ:

تشغيل الكود

جافا

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:صاروخ:

تشغيل الكود

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

  • الدليل غير المشفر إلى جداول التجزئة والتجزئة
  • كيفية تنفيذ جدول تجزئة بسيط في JavaScript
  • وأوضح جداول التجزئة