מילון (מבנה נתונים)

מילון (באנגלית נקרא Dictionary, Map או Associative Array) הוא מבנה נתונים מופשט המגדיר אוסף של מפתחות וערכים. המילון מורכב ממיפוי חד-ערכי בין מפתח (Key) לערך (Value). הפעולה של מציאת הערך שמקושר למפתח מסוים נקראת חיפוש (ולעתים גם שליפה), והיא הפעולה החשובה ביותר שמאפשר המילון. לדוגמה, ספר-טלפונים יכול להיות ממומש באמצעות מילון - מיפוי שמות של אנשים (מפתחות) אל מספרי הטלפון שלהם (ערכים).

פעולות מילון

הממשק הבסיסי ביותר של מילון מגדיר את הפעלות הבאות:

• הוספה (Add) - פעולה המקבלת מפתח חדש וערך, ומוסיפה למילון מיפוי בין המפתח לערך.
• חיפוש (Lookup) - פעולה המקבלת מפתח, ומחזירה את הערך הממופה לאותו מפתח.
• מחיקה (Remove) - פעולה המקבלת מפתח ומוחקת אותו (ואת הערך הממופה אליו) מהמילון.
• החלפה (Reassign) - פעולה המקבלת מפתח קיים במילון וערך חדש, וממפה את המפתח לערך החדש (הערך הקודם נדרס ונמחק).

מימושים

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

המימושים הנפוצים ביותר למילון הם:

• מערך - מימוש מנוון של מילון. המפתחות הם מספרים טבעיים, ועל הערכים אין הגבלה כלשהי. סיבוכיות הוספה וחיפוש של איברים הינה $O\left(1\right)$ במקרה הגרוע ביותר. החיסרון הבולט של שימוש במערך הוא שיש להקצות מראש מקום בזיכרון כגודל המפתח הגדול ביותר שנרצה להכניס למילון, מה שגורם לביזבוז אדיר של זיכרון ואף הופך ללא-ריאלי לעתים קרובות. לדוגמה, אם נרצה להכניס למילון איבר בודד עם מפתח $2\cdot2^{30}$ (2 ג'יגה), נצטרך להקצות מראש 2 ג'יגה-בייט של זיכרון, מה שכמובן אינו אפשרי במחשב ביתי ממוצע.
• טבלת גיבוב - מימוש של מילון הבא לפתור את הבעיה המתוארת במימוש מערך באמצעות פונקציית גיבוב. מימוש זה מאפשר הוספה וחיפוש של מפתחות בסיבוכיות זמן של $O\left(1\right)$ בתוחלת ו-$O\left(n\right)$ במקרה הגרוע ביותר. טבלת גיבוב לא מאפשרת מיון, ואינה זוכרת את הסדר בו הוכנסו האיברים.
• עץ אדום שחור - מימוש של מילון המאפשר חיפוש והוספה של מפתחות בסיבוכיות זמן של $O\left(\log n\right)$ גם במקרה הגרוע. בנוסף, הוא מאפשר איטרציה ממוינת לפי סדר המפתחות.
• עץ B Plus - מימוש בעל יתרונות יחסיים עבור מילונים גדולים במיוחד (לדוגמה, מרשם האזרחים של משרד הפנים, או מילון אבן-שושן).

מילון בו המפתחות הם הערכים הוא למעשה קבוצה.