Loading AI tools
מבנה נתונים מופשט המגדיר אוסף של מפתחות וערכים מוויקיפדיה, האנציקלופדיה החופשית
מילון (באנגלית נקרא Dictionary, Map או Associative Array) הוא מבנה נתונים מופשט המגדיר אוסף של מפתחות וערכים. המילון מורכב ממיפוי חד-ערכי בין מפתח (Key) לערך (Value). הפעולה של מציאת הערך שמקושר למפתח מסוים נקראת חיפוש (ולעיתים גם שליפה), והיא הפעולה החשובה ביותר שמאפשר המילון. לדוגמה, ספר-טלפונים יכול להיות ממומש באמצעות מילון – מיפוי שמות של אנשים (מפתחות) אל מספרי הטלפון שלהם (ערכים).
מילון בו המפתחות הם הערכים מגדיר קבוצה.
הממשק הנפוץ של מילון כולל את הפעלות הבאות:
פעולות נפוצות נוספות: בדיקת מספר המפתחות, ויצירה של איטרטור למעבר על הזוגות (מפתח, ערך).
ישנם מספר מבני נתונים אשר ניתן להשתמש בהם כדי לממש מילון. ההבדלים בין המימושים השונים רבים, וכוללים את סיבוכיות הזמן והמקום של הפעולות השונות, תמיכה או אי-תמיכה במיון המילון לפי המפתחות, שמירת הסדר של הערכים שהוכנסו, וכמות הזיכרון שנדרשת על-מנת לאחסן את מבנה הנתונים (בזיכרון הפנימי של המחשב וכן בדיסק הקשיח). מימושים מורכבים של מילון מאפשרים גם איטרציה על המפתחות, איטרציה על הערכים, או איטרציה על הערכים והמפתחות בו-זמנית.
המימושים הנפוצים ביותר למילון הם:
מימוש באמצעות עצים או מערך ממויין דורש הגדרה של יחס סדר מלא בין המפתחות. מימוש באמצעות טבלת גיבוב דורש הגדרה של פונקציית גיבוב (למציאת התא המתאים בטבלה) ושל בדיקת שוויון (בין המפתחות שבאותו תא).
מימושים בעזרת עצים אינם דורשים דבר מבחינת מספר האיברים במילון, לעומת מימושים בעזרת מערך ממויין או טבלת-גיבוב הדורשים טיפול מיוחד בשינוי גודל המערך, ולכן סיבוכיות הזמן של פעולת הכנסה בודדת איננה צפויה (שלא כמו הסיבוכיות הממוצעת). למימושים בעזרת מערך לוקליות גבוהה ביחס למימושים בעזרת טבלאות גיבוב או עצים.
כל המימושים אוסרים שינוי לא מבוקר של מפתחות הנמצאים בתוך המילון.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.