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

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

89. במה שונה ArrayList מ-LinkedList?

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

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

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

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

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

90. במה שונה ArrayList מ-HashSet?

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

• ArrayList מיישמת את ממשק List , בעוד HashSet מיישמת את ממשק Set ;

• ב- ArrayList הגישה אפשרית לפי אינדקס אלמנטים: לפעולת get יש מורכבות אלגוריתמית של O(1) , וב- HashSet ניתן להשיג את האלמנט הנדרש רק בכוח גס, וזה מ- O(1) עד O(n) ;

• ArrayList מאפשר רכיבים כפולים. ב- HashSet, כל האלמנטים הם ייחודיים: הוספת אלמנט ל- HashSet שהאנלוגי שלו כבר קיים באוסף לא תעבוד (כפילויות נבדקות באמצעות hashcode, ומכאן שמו של אוסף זה);

• ArrayList מיושם באמצעות מערך פנימי, ו- HashSet מיושם באמצעות HashMap פנימי ;

• ArrayList שומר על סדר ההכנסה של האלמנטים, בעוד ש-HashSet הוא קבוצה לא מסודרת ואינו שומר על סדר האלמנטים;

• ArrayList מאפשר כל מספר של ערכים ריקים (null), ניתן להכניס רק ערך null אחד ל- HashSet (אחרי הכל, הייחודיות של האלמנטים).

91. מדוע יש מגוון כזה של יישומי מערך דינמי ב-Java?

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

92. מדוע יש מגוון כזה של יישומי אחסון ערך מפתח ב-Java?

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

93. כיצד למיין אוסף של אלמנטים?

הדבר הראשון שצריך לומר הוא שמחלקת רכיבי האוסף חייבת ליישם את ממשק Comparable ואת שיטת compareTo שלו . לחלופין, אתה צריך מחלקה שמיישמת Comaprator עם שיטת ההשוואה שלה . תוכלו לקרוא עליהם עוד בפוסט זה . שתי השיטות מציינות כיצד יש להשוות בין אובייקטים מסוג נתון. בעת מיון, זה חשוב ביותר, כי אתה צריך להבין את העיקרון שלפיו ניתן להשוות אלמנטים. הדרך העיקרית לעשות זאת היא ליישם Comparable , מיושם ישירות במחלקה שברצונך למיין. יחד עם זאת, השימוש ב- Comparator פחות נפוץ. נניח שאתה משתמש בכיתה מספריה כלשהי שאין לה יישום Comparable , אבל תצטרך למיין אותה איכשהו. מבלי שתוכל לשנות את הקוד של מחלקה זו (למעט על ידי הארכתו), תוכל לכתוב יישום של Comparator , שבו אתה מציין על איזה עיקרון אתה רוצה להשוות אובייקטים של מחלקה זו. ועוד דוגמה אחת. נניח שאתה צריך עקרונות שונים למיון חפצים מאותו סוג, אז אתה כותב כמה Comparators שאתה משתמש בהם במצבים שונים. ככלל, מחלקות רבות מחוץ לקופסה כבר מיישמות את ממשק Comparable - אותה מחרוזת . למעשה, כשאתה משתמש בהם, אתה לא צריך לדאוג איך להשוות ביניהם. אתה פשוט לוקח אותם ומשתמש בהם. הדרך הראשונה והברורה ביותר היא להשתמש באוסף מסוג TreeSet או TreeMap , המאחסן את האלמנטים בסדר ממוין כבר על פי ה-element class comparator. זכור ש- TreeMap ממיין מפתחות, אך לא ערכים. אם אתה משתמש ביישום Comparator במקום Comparable , תצטרך להעביר את האובייקט שלו לבנאי האוסף עם היצירה:

TreeSet treeSet = new TreeSet(customComparator);

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

Collections.sort(someList);

אם אינך משתמש ב- Comparable , אלא ביישום של Comparator , עליך להעביר אותו כפרמטר השני:

Collections.sort(someList, customComparator);

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

someList = someList.stream().sorted().collect(Collectors.toList());

אם המשווה :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

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

ClassObject. שווה ו-HashCode

94. תן תיאור קצר של אובייקט המחלקה ב-Java

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

95. לשם מה משמשים Equals ו-HashCode ב-Java?

hashCode() היא שיטה של ​​מחלקת Object שעוברת בירושה לכל המחלקות. המשימה שלו היא ליצור מספר כלשהו שמייצג אובייקט ספציפי. דוגמה לשימוש בשיטה זו היא השימוש בה ב- HashMap על אובייקט מפתח כדי לקבוע עוד יותר את ה-hashcode המקומי, אשר יקבע את התא של המערך הפנימי (bucket) בו יאוחסן הזוג. דיברנו בפירוט על העבודה של HashMap בחלק 9 של הניתוח , אז לא נתעכב על זה יותר מדי. כמו כן, ככלל, שיטה זו משמשת בשיטת equals() כאחד הכלים העיקריים שלה לקביעת זהות אובייקטים. equals() היא שיטה של ​​המחלקה Object שתפקידה להשוות אובייקטים ולקבוע אם הם שווים או לא. שיטה זו משמשת בכל מקום בו אנו צריכים להשוות אובייקטים, מכיוון שההשוואה הרגילה באמצעות == אינה מתאימה לאובייקטים, כי משווה רק קישורים אליהם.

96. ספר לנו על החוזה בין Equals לבין HashCode ב-Java?

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

• אובייקטים זהים שעבורם השוואה באמצעות equals מחזירה true חייבים להיות בעלי קודי hash זהים;
• אובייקטים עם אותם קודי Hash עשויים שלא תמיד להיות שווים.

בשלב זה נעצור עד לחלק הבא של הניתוח!