שאלות ראיונות באוספי ג'אווה

מאמר זה הוא חלק מסדרה: • שאלות על ראיונות עם אוספי Java (מאמר נוכחי) • שאלות על ראיונות מערכת מסוג Java

• שאלות על ראיונות במקביל ל- Java (+ תשובות)

• שאלות על ראיונות מבנה כיתת Java ו אתחול

• Java 8 שאלות ראיונות (+ תשובות)

• ניהול זיכרון בשאלות ראיון עם Java (+ תשובות)

• שאלות ראיונות עם Java Generics (+ תשובות)

• שאלות ראיונות עם בקרת זרימת Java (+ תשובות)

• שאלות על ראיונות חריגים עם Java (+ תשובות)

• שאלות ראיונות בהערות Java (+ תשובות)

• שאלות על ראיונות מסגרת האביב המובילה

1. הקדמה

אוספי ג'אווה הוא נושא המועלה לעיתים קרובות בראיונות טכניים עבור מפתחי ג'אווה. מאמר זה סוקר כמה שאלות חשובות שנשאלות בתדירות הגבוהה ביותר ועשויות להיות מסובכות להגיע נכון.

2. שאלות

שאלה 1. תאר את היררכיית סוג האוספים. מהם הממשקים העיקריים ומה ההבדלים ביניהם?

ה ניתן לנידון ממשק מייצג כל אוסף שניתן לאתר באמצעות לכל אחד לוּלָאָה. ה אוסף ממשק יורש מ ניתן לנידון ומוסיף שיטות כלליות לבדיקה אם אלמנט נמצא באוסף, הוספה והסרה של אלמנטים מהאוסף, קביעת גודלו וכו '.

ה רשימה, מַעֲרֶכֶת, ו תוֹר ממשקים יורשים מה- אוסף מִמְשָׁק.

רשימה הוא אוסף מסודר, וניתן לגשת לאלמנטים שלו באמצעות האינדקס שלהם ברשימה.

מַעֲרֶכֶת הוא אוסף לא מסודר עם אלמנטים מובחנים, הדומים לתפיסה המתמטית של סט.

תוֹר הוא אוסף עם שיטות נוספות להוספה, הסרה ובחינת אלמנטים, שימושי להחזקת אלמנטים לפני העיבוד.

מַפָּה ממשק הוא גם חלק ממסגרת האיסוף, אך הוא אינו מתרחב אוסף. זה על ידי עיצוב, כדי להדגיש את ההבדל בין אוספים למיפויים שקשה לאסוף תחת מופשט משותף. ה מַפָּה ממשק מייצג מבנה נתונים בעל ערך מפתח עם מפתחות ייחודיים ולא יותר מערך אחד עבור כל מפתח.

שאלה 2. תאר יישומים שונים של ממשק המפה והבדלי השימוש בהם.

אחד היישומים הנפוצים ביותר של ה- מַפָּה ממשק הוא ה- מפת גיבוב. זהו מבנה נתוני מפת חשיש אופייני המאפשר גישה לגורמים בזמן קבוע, או O (1), אך אינו שומר על הסדר ואינו בטיחות חוטים.

כדי לשמור על סדר ההכנסה של אלמנטים, אתה יכול להשתמש ב- LinkedHashMap כיתה המרחיבה את מפת גיבוב ובנוסף קושר את האלמנטים לרשימה מקושרת, עם תקורה צפויה.

ה TreeMap class מאחסן את האלמנטים שלה במבנה עץ אדום-שחור, המאפשר גישה לאלמנטים בזמן לוגריתמי, או O (log (n)). זה איטי יותר מ- מפת גיבוב ברוב המקרים, אך זה מאפשר לשמור על סדר ביסודות לפי חלקם משווה.

ה ConcurrentHashMap הוא יישום בטוח של פתיל חשיש. הוא מספק מקבילות אחזוריות מלאה (כמו ה- לקבל הפעולה אינה כרוכה בנעילה) ובמקביל לעדכונים גבוהים.

ה טבלת גיבוב המחלקה קיימת בג'אווה מאז גרסה 1.0. זה לא הוצא משימוש אבל נחשב בעיקר למיושן. זוהי מפת חשיש בטוחה לחוטים, אך שלא כמו ConcurrentHashMap, כל השיטות שלה פשוטות מסונכרן, כלומר כל הפעולות במפה זו חוסמות, אפילו אחזור ערכים עצמאיים.

שאלה 3. הסבר את ההבדל בין קישור לרשימה ומערך.

רשימת מערך הוא יישום של רשימה ממשק שמבוסס על מערך. רשימת מערך מטפלת באופן פנימי בשינוי גודל של מערך זה כאשר הרכיבים מתווספים או מוסרים. אתה יכול לגשת לאלמנטים שלו בזמן קבוע על ידי האינדקס שלהם במערך. עם זאת, הוספה או הסרה של אלמנט מביאה לשינוי כל האלמנטים הנובעים מכך שעשויים להיות איטיים אם המערך ענק והאלמנט שהוכנס או הוסר קרוב לתחילת הרשימה.

רשימה מקושרת היא רשימה המקושרת כפליים: מכניסים אלמנטים בודדים צוֹמֶת אובייקטים שיש להם הפניות לקודם ולאחריו צוֹמֶת. יישום זה עשוי להיראות יעיל יותר מ- רשימת מערך אם יש לך הרבה הכנסות או מחיקות בחלקים שונים של הרשימה, במיוחד אם הרשימה גדולה.

ברוב המקרים, לעומת זאת, רשימת מערך עולה על ביצועים טובים יותר רשימה מקושרת. אפילו אלמנטים שעוברים פנימה רשימת מערך, בעודו מבצע O (n), מיושם כמהיר מאוד System.arraycopy () שִׂיחָה. זה יכול להופיע אפילו מהר יותר מה- רשימה מקושרתהכנסת O (1) הדורשת התקנת a צוֹמֶת התנגדות ועדכון מספר הפניות מתחת למכסה המנוע. רשימה מקושרת יכול גם להיות בעל זיכרון תקורה גדול עקב יצירה של מספר קטן צוֹמֶת חפצים.

שאלה 4. מה ההבדל בין Hashset ל- Treeset?

שניהם HashSet ו TreeSet שיעורים מיישמים את מַעֲרֶכֶת ממשק ומייצג קבוצות של אלמנטים מובחנים. בנוסף, TreeSet מיישם את ניווט ניווט מִמְשָׁק. ממשק זה מגדיר שיטות המנצלות את הזמנת האלמנטים.

HashSet מבוסס פנימי על א מפת גיבוב, ו TreeSet מגובה על ידי TreeMap למשל, המגדיר את המאפיינים שלהם: HashSet אינו שומר על אלמנטים בסדר מסוים כלשהו. איטרציה על היסודות בא HashSet מייצר אותם בסדר מעורב. TreeSet, לעומת זאת, מייצר אלמנטים לפי סדר לפי כמה שהוגדרו מראש משווה.

ש 5. כיצד מיישמים את Hashmap בג'אווה? כיצד מיושמתה משתמשת בהאשקוד ובשיטות שוות של אובייקטים? מה מורכבות הזמן של הצבת וקבלת אלמנט ממבנה כזה?

ה מפת גיבוב מחלקה מייצגת מבנה נתוני מפות חשיש אופייני עם אפשרויות עיצוב מסוימות.

ה מפת גיבוב מגובה במערך הניתן לשינוי גודל שיש לו כוח של שניים. כאשר האלמנט מתווסף ל- a מפת גיבוב, הראשון שלה hashCode מחושב (an int ערך). ואז מספר מסוים של סיביות נמוכות יותר של ערך זה משמש כאינדקס מערך. אינדקס זה מצביע ישירות על התא של המערך (הנקרא דלי) שבו צריך להיות ממוקם זוג ערך מפתח זה. גישה לאלמנט על ידי האינדקס שלו במערך היא פעולה מהירה מאוד O (1), שהיא המאפיין העיקרי של מבנה מפת hash.

א hashCode אינו ייחודי, עם זאת, ואפילו עבור שונה hashCodes, אנו עשויים לקבל את אותו מיקום מערך. זה נקרא התנגשות. יש יותר מדרך אחת לפתור התנגשויות במבני נתוני מפת החשיש. בג'אווה מפת גיבוב, כל דלי מתייחס למעשה לא לאובייקט יחיד, אלא לעץ אדום-שחור של כל האובייקטים שנחתו בדלי זה (לפני Java 8 זו הייתה רשימה מקושרת).

אז כאשר ה- מפת גיבוב קבע את הדלי למפתח, עליו לעבור על העץ הזה כדי להציב את צמד ערכי המפתח במקומו. אם כבר קיים זוג עם מפתח כזה בדלי, הוא מוחלף בזו חדשה.

כדי לאחזר את האובייקט באמצעות המפתח שלו, ה- מפת גיבוב שוב צריך לחשב את hashCode עבור המפתח, מצא את הדלי המתאים, חצה את העץ, התקשר שווים על המקשים בעץ ומצא את התואם.

מפת גיבוב יש מורכבות O (1), או מורכבות בזמן קבוע, של הצבת וקבלת האלמנטים. כמובן, הרבה התנגשויות עלולות לפגוע בביצועים למורכבות הזמן O (log (n)) במקרה הגרוע ביותר, כאשר כל האלמנטים נוחתים בדלי אחד. זה נפתר בדרך כלל על ידי מתן פונקציית חשיש טובה עם התפלגות אחידה.

כאשר מפת גיבוב המערך הפנימי מתמלא (עוד על כך בשאלה הבאה), הגודל שלו באופן אוטומטי יהיה גדול פי שניים. פעולה זו מביאה לשטיפה מחודשת (בנייה מחדש של מבני נתונים פנימיים), וזה יקר, לכן עליכם לתכנן את גודל מפת גיבוב מִרֹאשׁ.

שאלה 6. מה מטרת הפרמטרים הראשוניים של קיבולת ועומס עומס של Hashmap? מהם ערכי ברירת המחדל שלהם?

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

גורם העומס של א מפת גיבוב הוא היחס בין ספירת האלמנטים חלקי ספירת הדלי (כלומר גודל המערך הפנימי). למשל, אם 16 דלי מפת גיבוב מכיל 12 אלמנטים, מקדם העומס שלו הוא 12/16 = 0.75. גורם עומס גבוה פירושו הרבה התנגשויות, מה שאומר בתורו שיש לשנות את גודל המפה לכוח הבא של שניים. אז ה loadFactor ארגומנט הוא ערך מקסימלי של גורם העומס של מפה. כאשר המפה משיגה גורם עומס זה, היא משנה את גודל המערך הפנימי לערך כוח-שניים הבא.

ה initialCapacity הוא 16 כברירת מחדל, וה- loadFactor הוא 0.75 כברירת מחדל, כך שתוכל להכניס 12 אלמנטים ל- a מפת גיבוב שהופעל על ידי קונסטרוקטור ברירת המחדל, והוא לא ישתנה. כנ"ל לגבי HashSet, המגובה על ידי א מפת גיבוב מקרה פנימי.

כתוצאה מכך, זה לא טריוויאלי לעלות initialCapacity המספק את צרכיך. זו הסיבה שבספריית גויאבה יש Maps.newHashMapWithExpectedSize () ו Sets.newHashSetWithExpectedSize () שיטות המאפשרות לך לבנות מפת גיבוב או א HashSet שיכול להכיל את מספר האלמנטים הצפוי ללא שינוי גודל.

ש 7. תאר אוספים מיוחדים לאנומות. מה היתרונות של יישומם בהשוואה לאוספים רגילים?

EnumSet ו EnumMap הם יישומים מיוחדים של מַעֲרֶכֶת ו מַפָּה ממשקים בהתאם. אתה תמיד צריך להשתמש ביישומים אלה כאשר אתה מתמודד עם enums כי הם יעילים מאוד.

An EnumSet הוא רק קצת וקטור עם "אלה" במיקומים התואמים לערכים סדירים של enums הקיימים בערכה. כדי לבדוק אם ערך enum נמצא בערכה, היישום פשוט צריך לבדוק אם הביט המקביל בווקטור הוא "אחד", וזה פעולה קלה מאוד. באופן דומה, an EnumMap הוא מערך שניגש עם הערך הסדיר של enum כאינדקס. במקרה של EnumMap, אין צורך לחשב קודי hash או לפתור התנגשויות.

ש 8. מה ההבדל בין איטטורים מהירים לכישלון?

מחוונים לאוספים שונים הם מהירים או כשלים, תלוי איך הם מגיבים לשינויים מקבילים. השינוי במקביל אינו רק שינוי של אוסף משרשור אחר אלא גם שינוי מאותו שרשור אלא באמצעות איטרטור אחר או שינוי האוסף ישירות.

כישלון מהיר איטרטורים (אלה שהוחזרו על ידי מפת גיבוב, רשימת מערך, ואוספים אחרים שאינם בטוחים בחוטים) מתבטלים על פני מבנה הנתונים הפנימי של האוסף, והם זורקים ConcurrentModificationException ברגע שהם מזהים שינוי מקביל.

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

שאלה 9. כיצד ניתן להשתמש בממשקי השוואה והשוואה למיון אוספים?

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

ה ניתן להשוות ממשק מאפשר למיין רשימות של אובייקטים תואמים עם Collections.sort () שיטה ולקיים את צו האיטרציה באוספים המיישמים SortedSet ו SortedMap. אם ניתן למיין את האובייקטים שלך באמצעות הגיון כלשהו, ​​עליהם ליישם את ניתן להשוות מִמְשָׁק.

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

מחלקת האובייקטים שברצונך למיין אינה זקוקה ליישום ממשק זה. אתה פשוט יוצר כיתת יישום ומגדיר את ה- לְהַשְׁווֹת שיטה המקבלת שני עצמים ומחליטה כיצד להזמין אותם. לאחר מכן תוכל להשתמש במופע של מחלקה זו כדי לעקוף את הסדר הטבעי של ה- Collections.sort () שיטה או SortedSet ו SortedMap מקרים.

כמו ה משווה ממשק הוא ממשק פונקציונלי, אתה יכול להחליף אותו בביטוי למבדה, כמו בדוגמה הבאה. זה מראה הזמנת רשימה באמצעות הזמנה טבעית (מספר שלםשל ניתן להשוות ממשק) ושימוש באיטרטור מותאם אישית (משווה מִמְשָׁק).

רשימת רשימה 1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (רשימה 1); assertEquals (מספר שלם חדש (1), list1.get (0)); רשימת רשימה 1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (list1, (a, b) -> b - a); assertEquals (מספר שלם חדש (5), list1.get (0));
הַבָּא » שאלות על ראיונות מערכת מסוג Java