מה הם עשויים לשאול בראיון: מבני נתונים בג'אווה. חלק 2

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

6. ספר לנו על רשימה

רשימה היא ממשק המייצג מבנה מסודר של אובייקטים, הנקרא רשימה. ה"טריק" של מבנה זה הוא שניתן להוסיף, לשנות או למחוק את האלמנטים הכלולים ברשימה באמצעות אינדקס, כלומר המזהה הפנימי של הרשימה . במילים אחרות, אינדקס פירושו: "כמה אלמנטים יש מתחילת הרשימה." לאלמנט List הראשון יש אינדקס 0, לשני יש אינדקס 1 וכן הלאה. אז האלמנט החמישי רחוק ארבעה אלמנטים מתחילת הרשימה. כפי שהוזכר לעיל, הסדר שבו פריטים מתווספים לרשימה חשוב. לכן מבנה הנתונים נקרא רשימה . אנו מפרטים שיטות ייחודיות למבנה זה שמטרתן לעבוד עם אלמנטים לפי אינדקס:

• get - מחזיר את האלמנט במיקום שצוין (לפי ערך אינדקס),
• הסר - מסיר את האלמנט במיקום שצוין,
• set - מחליף את האלמנט במיקום שצוין באלמנט שצוין בשיטה.

המימושים העיקריים הם ArrayList ו- LinkedList . נדבר עליהם יותר מעט מאוחר יותר. וקטור היא רשימה בטוחה לשרשור, כך שכל שיטה במחלקה זו מסונכרנת. אבל זכור שאם אתה רוצה לאבטח כמה פעולות ברשימה, אתה תסנכרן רצף שלם של פעולות. וסינכרון פעולות בודדות הוא גם פחות בטוח וגם איטי בהרבה. כמובן, ל-Vector יש גם נעילה תקורה, גם אם אתה לא צריך את המנעול. לכן, מחלקה זו נחשבת כעת למיושנת ואינה בשימוש. דרך אגב: ArrayList דומה ל- Vector , אבל לא משתמשת בנעילה, ולכן משתמשים בה בכל מקום. Stack היא תת-מחלקה של המחלקה Vector עם בנאי ברירת מחדל אחד וכל השיטות של המחלקה Vector , ועוד כמה משלה (נדבר עליהן בהמשך). כדוגמה, אתה יכול לדמיין את התהליך כערימה של תיקיות עם מסמכים. אתה מציב תיקייה אחת בחלק העליון של הערימה, ואתה יכול לקחת את התיקיות האלה רק בסדר הפוך, החל מלמעלה. למעשה, זהו מנגנון מסוג LIFO , כלומר, Last In First Out , האחרון שיגיע הוא הראשון שיעזוב. המחסנית מיישמת שיטות משלה:

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

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

7. ספר לנו על מפה

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

• put(K key, V value) - הוספת אלמנט למפה;
• get(Object key) - חפש ערך לפי מפתח;
• containsKey(מפתח אובייקט) - בודק במפה את נוכחותו של מפתח זה;
• containsValue(Object value) - בודק במפה את נוכחותו של ערך זה;
• remove(Object key) - הסרת ערך על ידי המפתח שלו.

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

1. HashMap - מיועד לאחסן ערכים בסדר אקראי, אך מאפשר לך לחפש במהירות רכיבי מפה. מאפשר לך לציין מפתח באמצעות מילת המפתח null , אך לא יותר מפעם אחת, כי זוגות עם אותם מפתחות כתובים זה על גבי זה. התנאי העיקרי הוא הייחודיות של המפתחות: ניתן לחזור על הערכים (ייתכנו מספר ערכי אפס).
2. LinkedHashMap הוא אנלוגי של HashMap המאחסן ערכים לפי סדר הוספתם. בהתאם לכך, כמו LinkedList , יש לו כותרת - ראש רשימה מקושרת כפולה. כאשר הוא מאתחל, הוא מצביע על עצמו.

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

3. TreeMap היא מפה שממיינת אלמנטים לפי ערכי מפתח. דומה ל- TreeSet , אבל עבור זוגות המבוססים על ערכי מפתח. כדי להגדיר כללי מיון של TreeMap , המפתחות חייבים ליישם את ממשק Comparable . אחרת, צריך להיות Comparator מכוון Key (זה שצוין בבנאי TreeMap ), TreeSet - מיושם עם אובייקט TreeMap בתוכו, שבו, למעשה, כל הקסם מתרחש.

   תוכל לקרוא עוד על מיון ב-TreeMap באמצעות עצים אדומים-שחורים במאמר על התכונות של TreeMap .

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

8. ArrayList לעומת LinkedList. באיזה מהם עדיף להשתמש?

שאלה זו היא אולי הפופולרית ביותר במבני נתונים וטומנת בחובה כמה מלכודות. לפני שנענה על זה, בואו ללמוד עוד על מבני נתונים אלה. ArrayList מיישמת את ממשק List ופועלת על מערך פנימי המורחב לפי הצורך. כאשר המערך הפנימי מלא לחלוטין, ויש צורך להכניס אלמנט חדש, נוצר מערך חדש בגודל של (oldSize * 1.5) +1. לאחר מכן, כל הנתונים מהמערך הישן מועתקים לאלמנט חדש + חדש, והישן יימחק על ידי אספן האשפה . שיטת add מוסיפה אלמנט לתא הריק האחרון של המערך. כלומר, אם כבר יש לנו שם 3 אלמנטים, זה יוסיף את הבא לתא הרביעי. בואו נעבור על הביצועים של השיטות הבסיסיות:

• get(int index) - לקיחת אלמנט במערך לפי אינדקס היא המהירה ביותר ב- O(1) ;
• add(Object obj) - אם יש מספיק מקום במערך הפנימי עבור אלמנט חדש, אז עם הכנסה רגילה של O(1) יוקדש זמן , מכיוון שהתוספת ממוקדת לתא האחרון.

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

• remove(int index) - בעת הסרת אלמנט, למשל, מהאמצע, נקבל זמן O(n/2), שכן נצטרך להזיז את האלמנטים ימינה ממנו תא אחד אחורה. בהתאם לכך, אם מוחקים מתחילת הרשימה, אז O(n), מהסוף - O(1);
• add(int index, Object obj) - מצב דומה למחיקה: כאשר מוסיפים לאמצע, נצטרך להזיז את האלמנטים בתא הימני אחד קדימה, כך שהשעה היא O(n/2). כמובן, מההתחלה - O(n), מהסוף - O(1);
• set(int index, Object obj) - כאן המצב שונה, מכיוון שצריך רק למצוא את האלמנט הרצוי ולכתוב עליו מבלי להזיז את השאר, אז O(1).

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

• get(int index) - כאשר מחפשים אלמנט שנמצא באמצע הרשימה, הוא מתחיל לחפש את כל האלמנטים לפי הסדר עד שנמצא הרצוי. באופן הגיוני, החיפוש צריך לקחת O(n/2) , אבל ל-LinkedList יש גם זנב, כך שהחיפוש מתבצע בו זמנית משני הצדדים. בהתאם לכך, הזמן מצטמצם ל- O(n/4) .

  אם האלמנט קרוב לתחילת הרשימה או לסוף, אז הזמן יהיה O(1) ;

• add(Object obj) - בעת הוספת אלמנט חדש, לאלמנט "זנב" יתווסף קישור לאלמנט הבא, והחדש יקבל קישור לאלמנט הקודם ויהפוך ל"זנב" החדש. בהתאם לכך, הזמן יהיה O(1) ;
• remove(int index) - לוגיקה דומה לשיטת get(int index) . כדי להסיר אלמנט מאמצע הרשימה, תחילה עליך למצוא אותו. זה שוב O(n/4) , בעוד המחיקה עצמה למעשה לא לוקחת כלום, מכיוון שהיא רק משנה את המצביע של אובייקטים שכנים (הם מתחילים להתייחס זה לזה). אם האלמנט נמצא בהתחלה או בסוף, אז שוב - O(1) ;
• add(int index, Object obj) ו- set(int index, Object obj) - לשיטות תהיה מורכבות זמן זהה ל-get(int index) , מכיוון שרוב הזמן מושקע בחיפוש אחר האלמנט. לכן, עבור אמצע הרשימה - O(n/4) , עבור ההתחלה - O(1).

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

• הבחירה הטובה ביותר אם הפעולה השכיחה ביותר היא חיפוש אחר אלמנט, החלפת אלמנט;
• הבחירה הגרועה ביותר אם הפעולה היא הכנסה ומחיקה בהתחלה-אמצע, מכיוון שפעולות ההסטה של ​​אלמנטים מימין יתבצעו.

רשימה מקושרת:

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

9. כיצד מאוחסנים אלמנטים ב-HashMap?

אוסף HashMap מכיל טבלת מערך פנימית Node[] , שהתאים שלה נקראים גם buckets . הצומת מכיל:

• מפתח - קישור למפתח,
• ערך - התייחסות לערך,
• hash - ערך hash,
• הבא - קישור לצומת הבא .

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

1. המפתח נבדק עבור null . אם הוא null , אז המפתח יאוחסן בתא table[0] מכיוון שקוד ה-hash עבור null הוא תמיד 0.
2. אם המפתח אינו null , אזי שיטת ה-hashcode() של אובייקט המפתח נקראת , שתחזיר את קוד ה-hash שלו. קוד ה-hash הזה משמש לקביעת תא המערך שבו יאוחסן אובייקט ה-Node.
3. לאחר מכן, ה-hashcode הזה ממוקם בשיטת ה-hash() הפנימית , שמחשבת את ה-hashcode, אך בגודל של מערך הטבלה[] .
4. לאחר מכן, בהתאם לערך ה-hash, ה-Node ממוקם בתא ספציפי במערך הטבלה[] .
5. אם תא הטבלה[] המשמש לשמירת רכיב ה-Node הנוכחי אינו ריק, אך יש בו כבר אלמנט כלשהו, ​​אזי הרכיבים ה-Node עוברים על הערך הבא עד שמגיעים לאלמנט האחרון. כלומר, זה שהשדה הבא שלו הוא ריק .

   במהלך חיפוש זה, המפתח של אובייקט הצומת המוגן מושווה למפתחות של אלה שמחפשים:

   • אם נמצאה התאמה, החיפוש יסתיים, והצומת החדש יחליף את הצומת שבו נמצאה ההתאמה (רק שדה הערך שלו ידרוס );
   • אם לא נמצאו התאמות מפתח, הצומת החדש יהפוך לאחרון ברשימה הזו, ולקודם יהיה קישור הבא אליו.

לעתים קרובות עולה השאלה במהלך ראיונות: מהו קונפליקט ? המצב שבו תא של מערך הטבלה[] מאחסן לא אלמנט אחד, אלא שרשרת של שניים או יותר, נקרא התנגשות . במקרים רגילים שבהם רק אלמנט אחד מאוחסן בתא אחד בטבלה[] , לגישה לאלמנטים של HashMap יש מורכבות זמן קבועה של O(1) . אבל כאשר תא עם האלמנט הרצוי מכיל שרשרת של אלמנטים ( collision ), אז O(n) , שכן במקרה זה הזמן עומד ביחס ישר למספר האלמנטים הממוינים.

10. הסבר על איטרטור

בתרשים מיפוי ההיררכיה של Collection למעלה, ממשק האוסף היה המקום שבו התחילה כל ההיררכיה, אבל בפועל זה לא ממש ככה. האוסף יורש מממשק עם שיטת iterator() , אשר מחזירה אובייקט שמיישם את ממשק Iterator<E> . ממשק Iterator נראה כך:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - על ידי קריאה לשיטה זו, אתה יכול לקבל את האלמנט הבא. hasNext() - מאפשר לברר האם יש אלמנט הבא, והאם הגענו לסוף האוסף. וכשיש עדיין אלמנטים, hasNext() יחזיר true . בדרך כלל, hasNext() נקרא לפני המתודה next() , מכיוון ש- next() יזרוק NoSuchElementException כאשר הוא יגיע לסוף האוסף . remove() - מסיר את האלמנט שאוחזר בקריאה האחרונה ל-next() . מטרת איטרטור היא לבצע איטרציה על אלמנטים. לדוגמה:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

למעשה, הלולאה של כל אחד מיושמת מתחת למכסה המנוע באמצעות איטרטור. אתה יכול לקרוא עוד על זה כאן . List מספקת גרסה משלה של איטרטור, אבל גרסה מגניבה ומתוחכמת יותר - ListIterator . ממשק זה מרחיב את Iterator ויש לו שיטות נוספות:

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

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