שיעור 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).