ניתוח שאלות ותשובות מראיונות למפתח Java. חלק 9

זִקוּקֵי דִי נוּר! להיות מתכנת זה לא קל. אתה צריך כל הזמן ללמוד, תמיד ללמוד משהו חדש. אבל, כמו בכל עסק אחר, הדבר הכי קשה הוא להתחיל, לעשות את הצעד הראשון לקראת המטרה שלך. ומכיוון שאתה יושב באתר זה וקורא את המאמר הזה, סיימת את הצעד הראשון. זה אומר שעכשיו אתה צריך לנוע בכוונה לעבר המטרה שלך, מבלי להאט או להסתובב בדרך. אם אני מבין נכון, המטרה שלך היא להפוך למפתח Java או לשפר את הידע שלך אם אתה כזה. אם כן, אז אתה במקום הנכון, כי אנחנו נמשיך לנתח רשימה נרחבת של 250+ שאלות ראיונות למפתחי Java. בוא נמשיך!

אוספים

84. ספר לנו על איטרטורים והשימוש בהם

אוספים הם אחד מהנושאים האהובים בכל ראיון מפתח Java, וכאשר מדברים על היררכיית האוספים, המועמדים אומרים לעתים קרובות שזה מתחיל בממשק האוסף . אבל זה לא נכון, כי מעל הממשק הזה יש עוד אחד - Iterable . ממשק זה מייצג את שיטת iterator() , המאפשרת לך לקרוא לאובייקט Iterator עבור האוסף הנוכחי. ומה זה בדיוק האובייקט האיטרטור הזה ? איטרטור הוא אובייקט המספק את היכולת לעבור דרך אוסף ולחזור על אלמנטים מבלי שהמשתמש צריך לדעת את היישום של אוסף מסוים. כלומר, זהו סוג של מצביע על מרכיבי הקולקציה, שכביכול מסתכלים על מקום מסוים בו. לאיטרטור יש את השיטות הבאות:

• hasNext() - מחזירה true אם יש אלמנט הממוקם אחרי המצביע (שיטה זו מאפשרת לברר האם הגענו לסוף האוסף);
• next() - מחזיר את האלמנט הבא אחרי המצביע. אם אין, NoSuchElementException נזרק . כלומר, לפני השימוש בשיטה זו, עדיף לוודא שהאלמנט קיים - באמצעות hasNext() ;
• remove() - מסיר את האלמנט האחרון שהתקבל מהאוסף באמצעות השיטה next() . אם ל-next() מעולם לא נקרא לפני שנקרא remove() , ייגרם חריג - IllegalStateException ;
• forEachRemaining(<Consumer>) - מבצע את הפעולה שעברה עם כל אלמנט של האוסף (השיטה הופיעה ב-Java 8).

הנה דוגמה קטנה של איטרציה דרך רשימה והסרת כל הרכיבים שלה באמצעות שיטות האיטרטור שנדונו:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

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

iterator.forEachRemaining(x -> System.out.print(x));

אבל לאחר מכן, האיטרטור יהפוך ללא מתאים לשימוש נוסף, מכיוון שהוא יחצה את כל הרשימה, ולאיטרטור רגיל אין שיטות לחזרה לאחור. כאן אנו ניגשים בהדרגה ל-LinkedList , כלומר לשיטת listIterator() שלה , המחזירה סוג מודרני של איטרטור - ListIterator . מלבד שיטות האיטרטור הרגילות (הסטנדרטיות), לשיטות זה יש שיטות נוספות:

• add(<Element>) - מכניס אלמנט חדש לרשימה;
• hasPrevious() - מחזירה true אם יש אלמנט שנמצא לפני המצביע (בין אם יש אלמנט קודם);
• nextIndex() - מחזיר את האינדקס ברשימת האלמנט הבא אחרי המצביע;
• previous() - מחזיר את האלמנט הקודם (עד המצביע);
• previousIndex() - מחזיר את האינדקס של האלמנט הקודם;
• set(<Element>) - מחליף את האלמנט האחרון שהוחזר על ידי המתודות next() או previous() .

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

85. מהי היררכיית האוסף ב-Java Collection Framework?

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

• סט הוא ממשק המתאר מבנה נתונים כזה כקבוצה המכילה אלמנטים ייחודיים לא מסודרים (לא חוזרים). לממשק יש מימושים סטנדרטיים - TreeSet , HashSet ו- LinkedHashSet .
• רשימה היא ממשק המתאר מבנה נתונים המאחסן רצף מסודר של אובייקטים. ניתן להכניס ולמחוק מופעים הכלולים ברשימה לפי האינדקס שלהם באוסף זה (באנלוגי למערך, אך עם שינוי גודל דינמי). לממשק יש מימושים סטנדרטיים - ArrayList , Vector ( נחשב מיושן ולא בשימוש בפועל ) ו- LinkedList .
• Queue הוא ממשק המתאר מבנה נתונים המאחסן אלמנטים בצורה של תור העוקב אחר כלל FIFO-First In First Out . לממשק יש את ההטמעות הסטנדרטיות הבאות: LinkedList (כן, הוא מיישם גם Queue ) ו- PriotityQueue .

ההיררכיה השנייה של האוספים היא Map , שיש לה את המבנה הבא: באוסף זה אין חלוקות לתת-אוספים (שכן היררכיית המפה עצמה היא משהו כמו תת-אוסף, אבל שוכב בנפרד). יישומי מפה סטנדרטיים הם Hashtable (נחשב הוצא משימוש), LinkedHashMap ו- TreeMap . למעשה, כששואלים אותך לגבי אוסף , שתי ההיררכיות מתכוונות בדרך כלל.

86. מהו המבנה הפנימי של ArrayList?

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

<размерТекущегоМассива> * 3 / 2  + 1

כלומר, אם גודל המערך שלנו הוא 10, הגודל של המערך החדש יהיה: 10 * 3 / 2 + 1 = 16. לאחר מכן, כל הערכים מהמערך הראשון (הישן) מועתקים אליו באמצעות שיטת native System.arraycopy () , והמערך הראשון נמחק. למעשה, כך מיושמת ההרחבה הדינמית של ArrayList . בואו נסתכל על שיטות ArrayList הנפוצות ביותר : 1. add(<Elelement>) - מוסיף אלמנט לסוף המערך (לתא הריק האחרון), ובודק תחילה אם יש מקום במערך הזה. אם הוא לא שם, נוצר מערך חדש שאליו מועתקים האלמנטים. המורכבות הלוגריתמית של פעולה זו היא O(1). יש שיטה דומה - add(<Index>,<Elelement>) . הוא מוסיף אלמנט לא לסוף הרשימה (מערך), אלא לתא ספציפי עם האינדקס שהגיע כארגומנט. במקרה זה, המורכבות הלוגריתמית תהיה שונה בהתאם למקום שבו היא מתווספת:

• אם זו הייתה בערך תחילת הרשימה, המורכבות הלוגריתמית תהיה קרובה ל-O(N), מכיוון שכל האלמנטים הממוקמים מימין לחדש יצטרכו להזיז תא אחד ימינה;
• אם האלמנט מוכנס באמצע - O(N/2) כי עלינו להזיז רק מחצית ממרכיבי הרשימה תא אחד ימינה.

כלומר, המורכבות הלוגריתמית של שיטה זו נעה בין O(N) ל-O(1) בהתאם למקום בו האלמנט מוכנס. 2. set(<Index>,<Elelement>) - כותב אלמנט למיקום שצוין ברשימה. אם כבר יש אלמנט במיקום זה, מחליף אותו. המורכבות הלוגריתמית של הפעולה הזו היא O(1), כי אין תזוזות: רק חיפוש לפי אינדקס במערך, שכזכור יש לו מורכבות של O(1), וכתיבת האלמנט. 3. remove(<index>) - הסרת אלמנט לפי האינדקס שלו במערך הפנימי. בעת מחיקת פריט שאינו בסוף הרשימה, עליך להעביר את כל הפריטים מימין לו תא אחד שמאלה כדי לסגור את הפער שנותר לאחר מחיקת הפריט. לכן, המורכבות הלוגריתמית תהיה זהה ל- add(<Index>,<Elelement>) אם האלמנט היה באמצע - O(N/2) - כי צריך להזיז חצי מהאלמנטים אחד שמאלה. בהתאם, אם זה היה בהתחלה - O(N). ובכן, אם בסוף זה O(1), אין צורך להזיז שום דבר. למי שרוצה להעמיק בנושא זה, אשאיר קישור זה למאמר עם ניתוח של המחלקה ArrayList .

87. מהו המבנה הפנימי של LinkedList?

אם ArrayList מכיל אלמנטים במערך פנימי, אז LinkedList הוא בצורה של רשימה מקושרת כפולה. זה אומר שכל אלמנט מכיל קישור לאלמנט הקודם ( הקודם ) והבא הבא ( הבא ). לאלמנט הראשון אין קישור לקודם (הוא הראשון), אבל הוא נחשב לראש הרשימה, ול-LinkedList יש קישור ישירות אליו. לאלמנט האחרון, למעשה, אין אלמנט הבא, הוא הזנב של הרשימה, ולכן יש קישור ישיר אליו ב- LinkedList עצמו . לכן, המורכבות הלוגריתמית של גישה לראש או לזנב של רשימה היא O(1). ב- ArrayList, כשהרשימה גדלה, המערך הפנימי גדל, אבל כאן הכל קורה בצורה פשוטה יותר - כשמוסיפים אלמנט, כמה קישורים פשוט משתנים. בואו נסתכל על כמה מהשיטות הנפוצות ביותר של LinkedlList : 1. add(<Elelement>) - הוספה בסוף הרשימה, כלומר. לאחר האלמנט האחרון (5) יתווסף קישור לאלמנט החדש בתור הבא . לאלמנט החדש יהיה קישור אל האחרון (5) בתור האלמנט הקודם . המורכבות הלוגריתמית של פעולה כזו תהיה O(1), שכן יש צורך רק בקישור לאלמנט האחרון, וכזכור, לזנב יש קישור ישיר מ- LinkedList והמורכבות הלוגריתמית של הגישה אליו היא מינימלית. 2. add(<Index>,<Elelement>) - הוספת אלמנט לפי אינדקס. כאשר מוסיפים אלמנט, למשל, לאמצע רשימה, האלמנטים מהראש והזנב (משני הצדדים) עוברים תחילה עד למציאת המקום הרצוי. אם נרצה להכניס אלמנט בין השלישי לרביעי (בתמונה למעלה), אז כשמחפשים את המקום הנכון, הקישור הבא של האלמנט השלישי כבר יצביע על החדש. עבור החדש, הקישור הקודם יצביע על השלישי. בהתאם לכך, הקישור של האלמנט הרביעי - הקודם - כבר יצביע על האלמנט החדש, והקישור הבא של האלמנט החדש יצביע על האלמנט הרביעי: המורכבות הלוגריתמית של שיטה זו תהיה תלויה באינדקס שניתן ליסוד החדש:

• אם הוא קרוב לראש או לזנב, הוא יתקרב ל-O(1), מכיוון שלמעשה לא יהיה צורך לחזור על היסודות;
• אם הוא קרוב לאמצע, אז O(N/2) - האלמנטים מהראש והזנב ימוינו בו-זמנית עד למציאת האלמנט הדרוש.

3. set(<Index>,<Elelement>) - כותב אלמנט למיקום שצוין ברשימה. המורכבות הלוגריתמית של פעולה זו תנוע בין O(1) ל-O(N/2), שוב תלוי עד כמה האלמנט קרוב לראש, לזנב או לאמצע. 4. remove(<index>) - מסיר אלמנט מהרשימה, ובעצם הופך את האלמנט שמגיע לפני זה שהוסר ( הקודם ) להתייחס לאלמנט שבא אחרי זה שהוסר ( הבא ). ולהיפך: כך שהאלמנט שבא אחרי זה שנמחק מתייחס לזה שבא לפני זה שנמחק: התוצאה היא תהליך הפוך להוספה לפי אינדקס ( add(<Index>,<Elelement>) ). למי שרוצה ללמוד עוד על המבנה הפנימי של LinkedList , אני ממליץ לקרוא מאמר זה .

88. מהו המבנה הפנימי של HashMap?

אולי אחת השאלות הפופולריות ביותר בעת ראיון עם מפתח Java. HashMap v עובד עם צמדי מפתח-ערך . כיצד הם מאוחסנים בתוך ה-HashMapv עצמו ? בתוך HashMap יש מערך של צמתים:

Node<K,V>[] table

כברירת מחדל, גודל המערך הוא 16, והוא מכפיל את עצמו בכל פעם שהוא מתמלא באלמנטים (כאשר מגיעים ל-LOAD_FACTOR - אחוז מסוים של מלאות, כברירת מחדל הוא 0.75 ). כל צומת מאחסן hash של המפתח, מפתח, ערך וקישור לאלמנט הבא: למעשה, "קישור לאלמנט הבא" פירושו שאנו עוסקים ברשימה מקושרת בודדת, כאשר כל אלמנט מכיל קישור ל הבא. כלומר, HashMap מאחסנת נתונים במערך של רשימות מקושרות בודדות. אבל אציין מיד: כאשר לתא אחד של מערך הטבלה יש קישור לרשימה דומה עם קישור יחיד המורכב מיותר מאלמנט אחד, זה לא טוב. תופעה זו נקראת התנגשות . אבל דבר ראשון. בוא נראה איך זוג חדש נשמר בשיטת put . ראשית, ה-hachCode() של המפתח נלקח. לכן, כדי שה- hashmap תעבוד כהלכה , אתה צריך לקחת מחלקות שבהן שיטה זו נדחפת כמפתחות. לאחר מכן נעשה שימוש בקוד הגיבוב הזה בשיטה הפנימית - hash() - כדי לקבוע את המספר בגודל מערך הטבלה . לאחר מכן, באמצעות המספר שהתקבל, נגישות לתא ספציפי של מערך הטבלה . כאן יש לנו שני מקרים:

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

כאשר מחפשים אלמנט לפי מפתח ( get(<key>) method ), ה-hashCode של המפתח מחושב, ואז הערך שלו בתוך המערך באמצעות hash() , ובאמצעות המספר המתקבל, התא של מערך הטבלה נמצא , שבו החיפוש כבר מתבצע על ידי ספירת צמתים והשוואה בין המפתח של הצומת הרצוי למפתח הנוכחי. לפעולות במפה , במצב אידיאלי, יש מורכבות אלגוריתמית של O(1), מכיוון שהן ניגשות למערך, וכזכור, ללא קשר למספר האלמנטים, לפעולות על מערך יש מורכבות של O(1) . אבל זה אידיאלי. כאשר תא המערך שבו נעשה שימוש אינו ריק (2) וכבר יש שם כמה צמתים, המורכבות האלגוריתמית הופכת ל-O(N) לינארית, כי כעת יש צורך לבצע איטרציה על האלמנטים לפני מציאת המקום הנכון. אני לא יכול שלא להזכיר את זה: החל מ-Java 8, אם לצומת רשימה מקושרת יחידה יש ​​יותר מ-8 אלמנטים (התנגשויות), הוא הופך לעץ בינארי. במקרה זה, המורכבות האלגוריתמית כבר לא תהיה O(N), אלא O(log(N)) - זה כבר עניין אחר, לא? HashMap הוא נושא גדול, ואנשים אוהבים לשאול עליו שאלות בראיונות. לכן, אני ממליץ לך להבין את זה בפירוט (כדי שזה יקפיץ לך את השיניים). באופן אישי, לא היה לי ראיון בלי שאלות HashMap . אתה יכול למצוא צלילה עמוקה לתוך HashMap במאמר זה . זה הכל להיום, להמשך...