Розбір запитань та відповідей із співбесід на Java-розробника. Частина 10

Вітання! Як багато годин потрібно витратити, щоб стати чимось майстром? Часто чув щось на зразок: “Щоб стати майстром у будь-якій справі, потрібно витратити 10 000 годин”. Жахлива цифра, чи не так? Проте, мені цікаво, а чи це правда? І я постійно намагаюся прикидати, скільки годин я вже вклав у оволодіння програмістським мистецтвом. І коли я перейду ті заповітні 10000 годин і стану майстром, чи я відчую цю різницю? Чи я їх уже давно переступив, не усвідомивши цього? Так чи інакше, щоб стати програмістом, не потрібно вкладати таку величезну кількість часу. Головне - використовувати його з розумом. Ваша першорядна мета – пройти співбесіду. А на співбесідах новачків насамперед питають теорію, тому ви повинні бути в ній сильні. Власне, при самій підготовці до співбесіди, ваше завдання — виявити всі ваші прогалини в базовій теорії Java-розробника і покрити їх знаннями. І сьогодні я вам допоможу у цій справі, адже я тут, щоб продовжити розбір найпопулярніших питань. Отже, продовжимо!

89. Чим відрізняється ArrayList від LinkedList?

Це одне з найпопулярніших питань нарівні з питанням про внутрішній пристрій HashMap . Жодна співбесіда не обходиться без неї, і тому відповідь на неї у вас має “відсякувати від зубів”. Крім очевидної — різної назви, вони відрізняються внутрішнім пристроєм. Раніше ми розбирали внутрішній пристрій і ArrayList -а і LinkedList -а, тому вдаватися в деталі їх реалізації я не буду. Лише нагадаю, що ArrayList реалізований на основі внутрішнього масиву, який за потребою збільшується за формулою:

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

У той же час LinkedList реалізований на основі внутрішнього двозв'язкового списку, тобто кожен елемент має посилання на попередній і наступний, за винятком значень, які є початком/кінцем списку. Це питання люблять ставити у форматі: "Що краще - ArrayList або LinkedList ?", Сподіваючись вас підловити. Адже якщо ви як відповідь вкажете на одну з них, це буде неправильна відповідь. Натомість вам варто уточнити, про яку конкретну ситуацію йдеться - доступ за індексом або вставка в середину списку. Залежно від відповіді, ви зможете пояснити свій вибір. Раніше я вже описував, як працює ArrayList та LinkedListу тій чи іншій ситуації. Давайте підсумуємо це, поставивши в один ряд для порівняння: Додавання елемента (add)

1. Додавання нового елемента без вказівки індексу як розташування буде відбуватися автоматично до кінця обох списків. У LinkedList новий елемент стане новим хвостом (відбувається лише перезаписування пари посилань - алгоритмічна складність O(1) ).

   В ArrayList буде додано новий елемент в останню порожню комірку масиву - O(1) .

2. Додавання елемента за індексом зазвичай має на увазі вставку приблизно в середину списку. У LinkedList спершу вестиметься пошук потрібного місця за допомогою перебору елементів з "хвоста" і "голови" - O(n/2) , а потім - вставка значення шляхом перевизначення посилань елементів, між якими вставляється новий - O(1) . Сумарна алгоритмічна складність цієї дії буде O(n/2) .

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

3. Додавання елемента на початок списку в LinkedList буде ситуація схожа з додаванням в кінець: новий елемент стане новою "головою" - O (1) , в той же час коли ArrayList -у потрібно буде рухати всі елементи вправо - O (n) .

Підсумок: в LinkedList алгоритмічна складність коливатиметься від O(1) до O(n/2) . Тобто чим ближче вставка до кінця або початку списку, тим швидше. У той же час у ArrayList вона коливається від O(1) до O(n) : чим вставка ближче до кінця списку, тим швидше. Завдання елемента (set) Ця операція записує елемент у вказану позицію у списку, перезаписуючи попередній, якщо він є. У LinkedList ця операція схожа з додаванням, т.к. Найбільша складність тут - пошук елемента. Перезапис елемента проходитиме шляхом перезаписування пари посилань, тому тут також алгоритмічна складність коливатиметься відO(1) до O(n/2) залежно від віддаленості позиції від кінця чи початку списку. У той час в ArrayList для цієї операції за індексом буде знайдено потрібну комірку, а в неї записано новий елемент. Пошук за індексом, як і операція, має алгоритмічну складність O(1) . Взяти елемент за індексом (get) У LinkedList взяття елемента відбуватиметься за тим самим принципом, як і пошук інших операцій — залежно від віддаленості від кінця чи початку, тобто. від O(1) до O(n/2) . В ArrayList , як і раніше, пошук елемента в масиві за індексом має складність O(1) . Видалити елемент за індексом (remove) Для 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), в HashSet можна вставити лише одне значення null (як-не-як, унікальність елементів).

91. Навіщо в Java така різноманітність імплементації динамічного масиву?

Ну, це скоріше філософське питання. Ну а навіщо вигадують таку кількість нових різноманітних технологій? Для зручності. Власне, так само і з великою кількістю імплементацій динамічного масиву. Жодну з них не можна назвати кращою чи ідеальною. Кожна має перевагу в якійсь конкретній ситуації. І наше завдання — знати їхні відмінності, їх сильні/слабкі сторони: щоб зуміти в потрібній ситуації використовувати найкращу з них.

92. Навіщо в Java така різноманітність імплементацій key-value storage?

Тут ситуація така сама, як і з імплементаціями динамічного масиву. Однозначно найкращих немає: у кожної є сильні та слабкі сторони. І ми, звичайно, маємо максимально використовувати сильні сторони. Приклад: у пакеті concurrent, в якому є безліч багатопотокових технологій, є свої Concurrent колекції. У тій же ConcurrentHashMap є перевага в безпеці багатопоточної роботи з даними в порівнянні зі звичайною HashMap , але не в багатопоточному середовищі вона програє у швидкості роботи. Ну а імплементації, які в жодній із ситуацій не бувають найсильнішими, поступово перестають використовувати. Приклад: Hashtable , яка спочатку замислювалася як потокобезпечнаHashMap , але ConcurrentHashMap перевершила її при роботі в багатопотоковому середовищі, і в результаті про Hashtable забули і перестали використовувати.

93. Як сортувати колекцію елементів?

Перше, що треба сказати, клас елемента колекції повинен імплементувати інтерфейс Comparable і його метод compareTo . Або потрібен клас, який імплементує Comaprator з його методом comparator . Докладніше про них можна почитати в цьому пості . Обидва способи вказують, як потрібно порівнювати об'єкти даного типу. При сортуванні це є критично важливим, адже потрібно розуміти принцип, за яким елементи можна порівняти. В основному використовується спосіб через імплементацію Comparable , що реалізується безпосередньо в класі, який ви хочете сортувати. У той же час застосування Comparator-а рідше. Скажімо, ви використовуєте клас з якоїсь бібліотеки, яка не має реалізації Comparable , але вам якось потрібно буде його сортувати. Не маючи можливості змінити код цього класу (крім як розширити його), ви можете написати реалізацію Comparator -а, в якому вкажете, за яким принципом потрібно порівнювати об'єкти даного класу. І ще один приклад. Допустимо, вам потрібні різні принципи сортування об'єктів одного і того ж типу, тому ви пишете кілька Comparator -ів, які використовуєте в різних ситуаціях. Як правило, багато класів з коробки вже реалізують інтерфейс Comparable - той же String. Власне, при їх використанні вам не потрібно паритись, як їх порівняти. Ви просто берете та використовуєте їх. Перший і найочевидніший спосіб - використовувати колекцію типу TreeSet або TreeMap , які зберігають елементи в уже відсортованому порядку, згідно з компаратором класу елементів. Не забувайте, що TreeMap сортує ключі, але не значення. Якщо ви використовуєте імплементацію Comparator замість Comparable , вам потрібно буде передати його об'єкт у конструктор колекції під час створення:

TreeSet treeSet = new TreeSet(customComparator);

А якщо у вас колекція іншого типу? Як її відсортувати? І тут другий спосіб утилітного класу Collections — метод sort() . Він статичний, тому все, що вам потрібно – ім'я класу та метод, до якого передається необхідний список. Наприклад:

Collections.sort(someList);

Якщо ви використовуєте не Comparable , а Comparator , його потрібно передати другим параметром:

Collections.sort(someList, customComparator);

У результаті внутрішній порядок елементів переданого списку зміниться: його буде відсортовано відповідно до компаратора елементів. Зазначу, що список елементів має бути мутабельним, тобто. зміненим, інакше метод не спрацює і буде викинуто UnsupportedOperationException . Як третій спосіб можна використовувати Stream операцію sort , яка сортує елементи колекції, якщо використовується імплементація Comparable :

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

якщо Comparator :

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

Докладніше про Stream можна почитати у цій статті . Четвертий спосіб - ручна реалізація сортування, наприклад, сортування бульбашкою або сортування злиттям .

Class Object. Equals and HashCode

94. Дайте коротку характеристику class object Java

У другій частині розбору ми вже говорабо про методи класу Object , і я нагадаю, що клас Object — прабатько всіх класів Java. Він має 11 методів, які, відповідно, успадковуються всіма класами. Інформацію про всі 11 методів можна знайти у другій частині аналізу питань.

95. Для чого використовують Equals та HashCode у Java?

hashCode() - це метод класу Object , який успадковується всіма класами. Його завдання - генерування деякої кількості, що представляє конкретний об'єкт. Прикладом використання даного методу може бути його застосування в HashMap на об'єкті ключа для подальшого визначення локального хешкода, за яким визначиться комірка внутрішнього масиву (бакета), в якій буде збережено пару. Докладно про роботу HashMap ми говорабо в 9 частині розбору , тому особливо зупинятись на цьому не будемо. Також зазвичай цей метод використовується в методі equals() як один з його основних інструментів визначення ідентичності об'єктів. equals() - метод класуObject , завдання якого - порівнювати об'єкти і визначати, рівні вони чи ні. Цей метод використовується повсюдно там, де необхідно порівняти об'єкти, адже звичайне порівняння через == не підходить об'єктів, т.к. порівнює лише посилання ними.

96. Розкажіть про контракт між Equals та HashCode у Java?

Перше, що скажу, для коректної роботи методів equals() і hashCode() їх потрібно правильно перевизначити. Після цього вони повинні дотримуватися правил:

• однакові об'єкти, для яких порівняння через equals повертає true обов'язково мають однакові хеш - коди;
• об'єкти з однаковими хеш-кодами не завжди можуть бути рівними.

На цьому ми зробимо паузу до наступної частини розбору!