מילון (מבנה נתונים) – הבדלי גרסאות

* '''מחיקה''' (Remove) - פעולה המקבלת מפתח ומוחקת אותו (ואת הערך הממופה אליו) מהמילון.

* '''החלפה''' (Reassign) - פעולה המקבלת מפתח קיים במילון וערך חדש, וממפה את המפתח לערך החדש (הערך הקודם נדרס ונמחק).

== מימושים ==

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

 

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

* '''[[טבלת גיבוב]]''' - מימוש של מילון הבא לפתור את הבעיה המתוארת במימוש מערך באמצעות [[פונקציית גיבוב]]. מימוש זה מאפשר הוספה וחיפוש של מפתחות ב[[סיבוכיות זמן]] של <math>O\left(1\right)</math> ב[[תוחלת]] ו-<math>O\left(n\right)</math> במקרה הגרוע ביותר. טבלת גיבוב לא מאפשרת מיון, ואינה זוכרת את הסדר בו הוכנסו האיברים. זהו המימוש של מילון בשפת התכנות PERL. הוא נפוץ כל כך עד שרבים מכנים את מבנה הנתונים מילון בשם hash.

* '''[[עץ אדום שחור]]''' - מימוש של מילון המאפשר חיפוש והוספה של מפתחות בסיבוכיות זמן של <math>O\left(\log n\right)</math> גם במקרה הגרוע. בנוסף, הוא מאפשר איטרציה ממוינת לפי סדר המפתחות.