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

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

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

פעולות מילון

הממשק הנפוץ של מילון כולל את הפעלות הבאות:

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

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

מימושים

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

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

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

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

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

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