מבני הנתונים Set ו- Map

קטגוריה: מבני נתונים

דרגת קושי: 3



ברוב שפות התכנות המודרניות קיים מימוש כלשהו של מבני הנתונים 'Set',שמשמש לאחסון אוסף של אלמנטים ייחודיים, ו-'Map' (לעיתים נקרא גם 'Dictionary'), שמאחסן אוסף של זוגות מפתח-ערך (key value pairs).

  • לאיזה צורך משמש כל אחד ממבני הנתונים?
  • תאר את העיקרון של המימוש של מבני הנתונים הללו.
  • כיצד המימוש שהצעת משפיע על זמן הריצה הצפוי של פעולות נפוצות כמו הכנסה, חיפוש, ומחיקה?
  • כיצד מבני הנתונים הללו דומים זה לזה? במה הם שונים?

הוספת פתרון חדש

או התחבר

  • מתן, 20-06-24:

    למה משמשים מבני הנתונים Set ו- Map

    Set: מבנה נתונים שמאפשר אחסון של אלמנטים ייחודיים (לא מאפשר חזרות).
    Map (Dictionary): מבנה נתונים שמאחסן זוגות של מפתחות וערכים, כאשר כל מפתח הוא ייחודי.

    כיצד מממשים Set ו- Map

    מבני הנתונים Set ו-Map ניתנים למימוש באמצעות טבלאות גיבוב (hash tables).

    טבלת גיבוב היא קונספט בסיסי וחשוב במדעי המחשב. טבלת גיבוב מאוחסנת במערך. כדי להוסיף ערך X לטבלת גיבוב, אנחנו מפעילים על X את פונקציית הגיבוב. תוצאת הפונקציה קובעת את האינדקס במערך אליו נוסיף את X. חשוב לבנות את פונקציית הגיבוב באופן שתפזר את הערכים המוכנסים לתאי המערך במידה שווה ככל האפשר (אך במבני נתונים כמו Set ו- Map זה כבר ממומש בשפה עצמה ולא אחריות שלנו כמתכנתים).

    מימוש של Set באמצעות טבלת גיבוב:
    הכנסת אלמנט: כאשר מוסיפים אלמנט חדש, משתמשים בפונקצית הגיבוב כדי למצוא את האינדקס בו יש לשמור אותו. אם האינדקס כבר תפוס על ידי אלמנט אחר (התנגשות), משתמשים באסטרטגיות כמו גיבוב חוזר או שרשור פנימי כדי למצוא מקום פנוי.
    בדיקת קיום: כדי לבדוק אם אלמנט קיים ב-Set, מחשבים את ערך הגיבוב שלו ובודקים את המיקום המתאים במערך. 

    מימוש של Map באמצעות טבלת גיבוב:
    הכנסת זוג מפתח-ערך: כאשר מוסיפים זוג חדש, מפעילים את פונקצית הגיבוב על המפתח כדי למצוא את האינדקס במערך. אם כבר קיים זוג מפתח-ערך עם אותו מפתח באינדקס זה, הערך יעודכן. אם יש התנגשות (כלומר, זוג עם מפתח אחר כבר מופה לאינדקס הזה), משתמשים באותה אסטרטגיית פתרון התנגשויות כמו ב-Set.
    חיפוש וגישה לערכים: חיפוש ערך מתבצע לפי המפתח, מחשבים את גיבוב המפתח ומבצעים חיפוש באינדקס המתאים.

    השפעת המימוש על זמן הריצה:

    פעולות של הכנסה, חיפוש, ומחיקה בטבלת גיבוב הן בסיבוכיות זמן ממוצעת של O(1) (זמן קבוע). זה מושג על ידי שימוש בטבלת גיבוב, כפי שהוסבר קודם. חישוב פונקצית הגיבוב אורכת זמן קבוע ומוצאת את האינדקס הנכון במערך. התנגשויות יכולות להאריך את הזמן שפעולה אורכת (כך שפעולה יכולה לקחת במקרה הגרוע O(n), אבל מימושים חכמים של פונקציות גיבוב הופכים זאת לנדיר מאוד, והממוצע הוא O(1).