שאלת מבחן בתכנות מונחה עצמים - אוניברסיטת בר-אילן 2023 - מבני נתונים

(LinkedHash) בג'אווה, איך נממש מבנה נתונים שיש לו גם תכונות של רשימה מקושרת (LinkedList) וגם תכונות של HashSet? סמנו את המרכיב שסביר ביותר שנזדקק לו בפתרון. .1 נשתמש בממשק (interface) .2 נשתמש בהאצלה (delegation) .3 נשתמש בהורשה (inheritance) .4 נשתמש במחלקת בסיס מופשטת (abstract base class)

רמז: חשבו כיצד ניתן לשלב את הפונקציונליות של שתי מחלקות קיימות ונפרדות מבלי לרשת מהן, אלא על ידי החזקת מופעים שלהן כשדות פנימיים.

פתרון: התשובה הנכונה היא 2. **האצלה (delegation)**, או באופן קרוב **קומפוזיציה (composition)**, היא הדרך הנכונה לממש מבנה נתונים כזה. המטרה היא ליצור מבנה המשלב שתי תכונות מרכזיות: 1. אחסון ייחודי וחיפוש מהיר (בזמן ממוצע של $O(1)$) - תכונה של `HashSet`. 2. שמירה על סדר ההכנסה של האיברים - תכונה של `LinkedList`. נבחן את האפשרויות: * **הורשה (Inheritance):** לא ניתן להשתמש ב**ירושה** כפולה ממחלקות ב-Java, כלומר לא ניתן לרשת גם מ-`HashSet` וגם מ-`LinkedList` בו-זמנית. גם אם היינו יורשים מאחת מהן, היינו צריכים לממש מחדש את כל הפונקציונליות של השנייה, מה שמסבך את הפתרון ומפספס את המטרה של שימוש חוזר בקוד קיים. * **ממשק (Interface) או מחלקה מופשטת (Abstract Class):** כלים אלו מגדירים חוזה או התנהגות חלקית, אך אינם מספקים את המימוש המלא של שתי המחלקות הקונקרטיות שאנו רוצים לשלב. הפתרון הנכון והאלגנטי הוא להשתמש ב**האצלה**: המחלקה החדשה שלנו, `LinkedHash`, תחזיק בתוכה שני שדות פרטיים: 1. מופע של `HashSet<E>` (או `HashMap` במימוש 실제) לאחסון האיברים ולבדיקת קיום מהירה. 2. מופע של `LinkedList<E>` כדי לתעד את סדר ההכנסה. כך, פעולות שונות יואצלו למבנה הנתונים המתאים: * **פעולת `add(element)`:** ראשית, ננסה להוסיף את האיבר ל-`HashSet`. אם הפעולה מצליחה (כלומר, האיבר לא היה קיים קודם), נוסיף אותו גם לסוף ה-`LinkedList`. * **פעולת `contains(element)`:** תועבר ישירות ל-`HashSet` כדי לנצל את החיפוש המהיר ב-$O(1)$ בממוצע. * **איטרציה (Iteration):** תתבצע על ה-`LinkedList` כדי לשמור על סדר ההכנסה. גישה זו מאפשרת לשלב את ה"טוב מכל העולמות" של שני מבני הנתונים ביעילות, והיא דוגמה קלאסית לעיקרון התכנות "העדף קומפוזיציה על פני ירושה".