מילון (מבנה נתונים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Badidipedia (שיחה | תרומות) אין תקציר עריכה |
Matanyabot (שיחה | תרומות) מ בוט החלפות: אידיאל, לעיתים |
||
שורה 1:
'''מילון''' (ב[[אנגלית]] נקרא '''Dictionary''', '''Map''' או '''Associative Array''') הוא [[מבנה נתונים מופשט]] המגדיר אוסף של [[מפתח ראשי|מפתחות]] ו[[ערך (מתמטיקה)|ערכים]]. המילון מורכב מ[[פונקציה|מיפוי חד-ערכי]] בין '''מפתח''' (Key) ל'''ערך''' (Value). הפעולה של מציאת הערך שמקושר למפתח מסוים נקראת '''חיפוש''' (
מילון בו המפתחות הם הערכים מגדיר [[קבוצה (מבנה נתונים)|קבוצה]].
שורה 8:
* '''הוספה''' (Add) - פעולה המקבלת מפתח חדש וערך, ומוסיפה למילון מיפוי בין המפתח לערך.
* '''מחיקה''' (Remove) - פעולה המקבלת מפתח ומסירה אותו (ואת הערך הממופה אליו) מהמילון.
* '''החלפה''' (Reassign) - פעולה המקבלת מפתח קיים במילון וערך חדש, וממפה את המפתח לערך החדש (הערך הקודם נדרס ונמחק). ניתן לבצע פעולה זו בעזרת מחיקה והוספה, אך
פעולות נפוצות נוספות: בדיקת מספר המפתחות, ויצירה של איטרטור למעבר על הזוגות (מפתח, ערך).
שורה 16:
המימושים הנפוצים ביותר למילון הם:
* '''[[מערך (מבנה נתונים)|מערך]]''' - במקרה שבו המפתחות מהווים טווח צר של מספרים (או קיים מיפוי חד-ערכי פשוט מהמפתחות אל טווח צר של מספרים), וכאשר הערכים בטווח הם בעלי אותו טיפוס, ניתן לממש מילון על ידי הצבת הערכים כשהם רצופים בזיכרון, וביצוע המיפוי בזמן הגישה. כאשר המיפוי איננו מורכב יותר מפעולות חיסור או חיבור של מספר קבוע, מבנה זה נקרא מערך, והוא מקרה פרטי של טבלת גיבוב בה ידוע מראש שלא יהיו התנגשויות. מימוש זה הוא היעיל ביותר, מבחינת זמן הריצה, כאשר הוא ניתן לביצוע: זמן הגישה האסימפטוטי איננו תלוי במספר האיברים במערך. מידת היעילות בהיבט המקום עומדת ביחס ישר למידת צפיפות המפתחות בהם נעשה שימוש: עבור מפתחות צפופים מערך יהיה חסכוני במקום,
* '''[[טבלת גיבוב]]''' - מימוש של מילון הבא לפתור את הבעיה המתוארת במימוש מערך באמצעות [[פונקציית גיבוב]]. מימוש זה מאפשר הוספה וחיפוש של מפתחות ב[[סיבוכיות זמן]] של <math>O\left(1\right)</math> ב[[תוחלת]] אך <math>O\left(n\right)</math> במקרה הגרוע ביותר. טבלת גיבוב איננה מגדירה סדר מכל סוג שהוא. מימוש זה של מילון נפוץ מאוד, עד כדי כך שרבים מכנים את מבנה הנתונים מילון בשם hash או hashtable (טבלת גיבוב).
* '''[[עץ אדום שחור]]''' - מימוש של מילון המאפשר חיפוש והוספה של מפתחות בסיבוכיות זמן של <math>O\left(\log n\right)</math> גם במקרה הגרוע. בנוסף, הוא מאפשר איטרציה ממוינת לפי סדר המפתחות.
| |||