What is a Hash Table?
الدرس 2 من 14 في دورة جداول الهاش - سلسلة هياكل البيانات #4 على Coddy.
جدول التجزئة (hash table) هو هيكل بيانات يخزن أزواج المفتاح والقيمة، مثل القاموس الذي يبحث عن المدخلات بواسطة مفتاحها. السر يكمن في السرعة: جدول التجزئة المصمم جيدًا يجد، أو يدرج، أو يزيل مدخلاً في متوسط زمن قدره O(1)، بغض النظر عن عدد المدخلات التي يحتوي عليها.
الخدعة تكمن في دالة التجزئة (hash function). يتم تحويل كل مفتاح إلى مؤشر سلة (bucket index)، لذا نعرف بالضبط أين نبحث دون فحص الجدول بالكامل. عندما يستقر مفتاحان مختلفان في نفس السلة (يحدث تصادم - collision)، نحتفظ بهما معًا في قائمة عند تلك السلة. تسمى هذه الاستراتيجية التسلسل (chaining).
العمليات الخمس الرئيسية في جدول التجزئة هي:
- Put: تخزين زوج من المفتاح والقيمة، أو تحديث القيمة إذا كان المفتاح موجودًا بالفعل.
- Get: البحث عن القيمة لمفتاح معين.
- ContainsKey: التحقق مما إذا كان المفتاح مخزنًا في الجدول.
- Remove: حذف زوج المفتاح والقيمة.
- Size: إرجاع عدد الأزواج المخزنة حاليًا.
لنقم بإنشاء فئة HashMap!
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.