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

ישנם מספר מבני נתונים אשר ניתן להשתמש בהם כדי לממש מילון. ההבדלים בין המימושים השונים רבים, וכוללים את סיבוכיות הזמן והמקום של הפעולות השונות, תמיכה או אי-תמיכה במיון המילון לפי המפתחות, שמירת הסדר של הערכים שהוכנסו, וכמות הזיכרון שנדרשת על-מנת לאחסן את מבנה הנתונים (בזיכרון הפנימי של המחשב וכן בדיסק הקשיח). מימושים מורכבים של מילון מאפשרים גם איטרציה על המפתחות, איטרציה על הערכים, או איטרציה על הערכים והמפתחות בו-זמנית.
המימושים הנפוצים ביותר למילון הם:
מערך – במקרה שבו המפתחות מהווים טווח צר של מספרים (או קיים מיפוי חד-ערכי פשוט מהמפתחות אל טווח צר של מספרים), וכאשר הערכים בטווח הם בעלי אותו טיפוס, ניתן לממש מילון על ידי הצבת הערכים כשהם רצופים בזיכרון, וביצוע המיפוי בזמן הגישה. כאשר המיפוי איננו מורכב יותר מפעולות חיסור או חיבור של מספר קבוע, מבנה זה נקרא מערך, והוא מקרה פרטי של טבלת גיבוב בה ידוע מראש שלא יהיו התנגשויות. מימוש זה הוא היעיל ביותר, מבחינת זמן הריצה, כאשר הוא ניתן לביצוע: זמן הגישה האסימפטוטי איננו תלוי במספר האיברים במערך. מידת היעילות בהיבט המקום עומדת ביחס ישר למידת צפיפות המפתחות בהם נעשה שימוש: עבור מפתחות צפופים מערך יהיה חסכוני במקום, ואידיאלי כאשר נעשה שימוש בכל המפתחות. עבור מפתחות מפוזרים ייתכן כי טבלת גיבוב או עץ יהיו חסכוניים יותר.
טבלת גיבוב – מימוש של מילון הבא לפתור את הבעיה המתוארת במימוש מערך באמצעות פונקציית גיבוב. מימוש זה מאפשר הוספה וחיפוש של מפתחות בסיבוכיות זמן של  O\left(1\right) בתוחלת אך  O\left(n\right) במקרה הגרוע ביותר. טבלת גיבוב איננה מגדירה סדר מכל סוג שהוא. מימוש זה של מילון נפוץ מאוד, עד כדי כך שרבים מכנים את מבנה הנתונים מילון בשם hash או hashtable (טבלת גיבוב).
עץ אדום שחור – מימוש של מילון המאפשר חיפוש והוספה של מפתחות בסיבוכיות זמן של  O\left(\log n\right) גם במקרה הגרוע. בנוסף, הוא מאפשר איטרציה ממוינת לפי סדר המפתחות.
עץ B Plus – מימוש בעל יתרונות יחסיים עבור מילונים גדולים במיוחד (לדוגמה, מרשם האזרחים של משרד הפנים, או מילון אבן-שושן).
מערך ממויין – אם הבניה של המילון והגישה אליו הן שתי פאזות שונות, ואם מוגדר יחס סדר על האיברים, אפשר לבנות את המילון במערך לא ממויין, למיין אותו, ואז לבצע גישות באמצעות חיפוש בינארי. זהו מימוש של עץ חיפוש בינארי בסיבוכיות מקום נוסף  O\left(1\right), על חשבון סיבוכיות הזמן במעבר בין הפאזות.
מימוש באמצעות עצים או מערך ממויין דורש הגדרה של יחס סדר מלא בין המפתחות. מימוש באמצעות טבלת גיבוב דורש הגדרה של פונקציית גיבוב (למציאת התא המתאים בטבלה) ושל בדיקת שוויון (בין המפתחות שבאותו תא).
מימושים בעזרת עצים אינם דורשים דבר מבחינת מספר האיברים במילון, לעומת מימושים בעזרת מערך ממויין או טבלת-גיבוב הדורשים טיפול מיוחד בשינוי גודל המערך, ולכן סיבוכיות הזמן של פעולת הכנסה בודדת איננה צפויה (שלא כמו הסיבוכיות הממוצעת). למימושים בעזרת מערך לוקליות גבוהה ביחס למימושים בעזרת טבלאות גיבוב או עצים.
כל המימושים אוסרים שינוי לא מבוקר של מפתחות הנמצאים בתוך המילון.
| מבני נתונים |
| --- | --- | --- |
| מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות |  |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ |  |
| גרפים ועצים | ערימה  (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש  (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R‏ • Trie • X-fast trie • טריי y מהיר• עץ WAVL |  |
| הסתברותיים | מסנן בלום |  |