الدرس 6: hash maps وعدّ التكرارات
تخيّل قاموسًا: أنت لا تقرأه من البداية، بل تقفز مباشرة إلى الكلمة وتحصل على معناها. هذا بالضبط ما تفعله hash map (في Python: dict) — بنية من أزواج مفتاح-قيمة تقفز مباشرة إلى المفتاح. فحص 'هل رأيت هذا من قبل؟' الذي يستغرق O(n) عند مسح قائمة يصبح شبه فوري مع dict أو set — O(1) في المتوسط، مقابل قليل
hash map تشبه الفهرس في نهاية الكتاب: بدلًا من تقليب كل صفحة للعثور على كلمة (هذا 'مسح' بطيء)، تبحث عنها في الفهرس وتقفز مباشرة إلى الصفحة الصحيحة (هذا O(1) — فوري). الثمن؟ قليل من الورق الإضافي — أي قليل من الذاكرة الإضافية مقابل الكثير من السرعة.
- خريطة التجزئة (hash map)
- بنية تربط مفتاحًا بقيمة مع بحث وإدراج بزمن O(1) في المتوسط، عبر حساب عنوان مباشر من المفتاح. في Python هذه هي dict.
- المجموعة (set)
- مجموعة خالية من التكرارات تفحص الانتماء (هل العنصر موجود) بزمن O(1) في المتوسط — مفيدة لاكتشاف التكرارات وإزالتها.
- عدّ التكرارات
- عدّ كم مرة تظهر كل قيمة في المدخلات باستخدام dict يربط القيمة ← عدّاد، في مرور واحد بزمن O(n).
