ملخص Hash Table للمقابلات البرمجية
مقدمة
الـHash Table (يُشار إليه عادةً بالـHash Map) هو هيكل بيانات يطبق نمط البيانات المجرد للـArray الترابطية، وهو هيكل يمكنه ربط المفاتيح بالقيم. يستخدم الـHash Table الـhash function على العنصر لحساب فهرس، يُسمى أيضاً الـhash code، ضمن Array من الحاويات أو الفتحات التي يمكن منها إيجاد القيمة المطلوبة. وأثناء البحث، يُجزّأ المفتاح ويشير الـhash code الناتج إلى مكان تخزين القيمة المقابلة.
التجزئة هي المثال الأكثر شيوعاً على المقايضة بين المساحة والزمن. فبدلاً من البحث خطياً في Array في كل مرة لتحديد ما إذا كان عنصر موجوداً، وهو ما يستغرق زمناً O(n)، يمكننا اجتياز الـArray مرة واحدة وتجزئة جميع العناصر في Hash Table. ويصبح تحديد وجود العنصر مسألة بسيطة تتمثل في تجزئة العنصر والتحقق من وجوده في الـHash Table، وهو O(1) في المتوسط.
في حالة تصادمات التجزئة، هناك عدد من تقنيات حل التصادم التي يمكن استخدامها. ومن غير المرجح أن تُسأل عن تفاصيل تقنيات حل التصادم في المقابلات:
- السلاسل المنفصلة — تُستخدم Linked List لكل قيمة، بحيث تخزن جميع العناصر المتصادمة.
- العنونة المفتوحة — تُخزن جميع سجلات الإدخال في Array الحاويات نفسها. وعندما يجب إدراج إدخال جديد، تُفحص الحاويات بدءاً من الفتحة التي أشارت إليها التجزئة وبالتتابع وفق تسلسل فحص معين، حتى يُعثر على فتحة غير مشغولة.
مصادر التعلم
- قراءات
- Taking Hash Tables Off The Shelf، basecs
- Hashing Out Hash Functions، basecs
- فيديوهات
- Core: Hash Tables، University of California San Diego
- A Brief Guide to Hash Tables (الشرائح)، Samuel Albanie، University of Cambridge
التطبيقات
| اللغة | واجهة برمجة التطبيقات |
|---|---|
| C++ | std::unordered_map |
| Java | java.util.Map. استخدم java.util.HashMap |
| Python | dict |
| JavaScript | Object أو Map |
الـtime complexity
| العملية | Big-O | ملاحظة |
|---|---|---|
| الوصول | غير متاح | الوصول غير ممكن لأن الـhash code غير معروف |
| البحث | O(1)* | |
| الإدراج | O(1)* | |
| الحذف | O(1)* |
* هذه هي الحالة المتوسطة، لكننا في المقابلات نهتم فقط بالحالة المتوسطة لHash Tables.
أسئلة نموذجية
- صف تطبيقاً لذاكرة تخزين مؤقت بالأقل استخداماً (least-used cache)، وترميز big-O له.
- سؤال يتضمن تكامل واجهة برمجة تطبيقات مع خريطة تجزئة تتكون حاوياتها من Linked Lists.
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.