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

Салют! Бути програмістом непросто. Потрібно постійно вчитися, завжди пізнавати щось нове. Але, як і в будь-якій іншій справі, найскладніше — почати зробити перший крок на шляху до своєї мети. І коли ти сидиш на даному сайті і читаєш цю статтю, з першим кроком ти впорався. Отже, тепер потрібно цілеспрямовано рухатися до своєї мети, не гальмуючи і не згортаючи по дорозі. Якщо я розумію правильно, твоя мета - стати Java-розробником або посаботи знання, якщо ти є таким. Якщо все так, то ти за адресаою, адже ми будемо продовжувати розбирати список з 250+ питань на співбесідах для Java-розробника. Продовжимо!

Collections

84. Розкажіть про ітератори та їх застосування

Колекції - одна з найулюбленіших тем на будь-якій співбесіді Java-розробника, і розповідаючи про ієрархію колекцій кандидати часто говорять, що вона починається з інтерфейсу Collection . Але це не так, адже над цим інтерфейсом є ще один – Iterable . Цей інтерфейс є методом iterator() , який дозволяє викликати об'єкт Iterator для поточної колекції. І що ж таке цей об'єкт 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() .

Як бачимо, функціонал цього ітератора набагато цікавіший: він дозволяє ходити в обидві сторони та розв'язує руки у роботі з елементами. Також коли говорять про ітераторів іноді мають на увазі сам патерн. Щоб не потрапити в халепу і розповісти про неї переконливо, читайте цю статтю про патерн Iterator .

85. Яка ієрархія колекцій у Java Collection Framework?

Існує дві ієрархії колекцій у Java. Перша ієрархія - безпосередньо ієрархія Collection з наступною структурою: Вона ділиться на наступні підколекції:

• Set - інтерфейс, що описує таку структуру даних як безліч , що містить невпорядковані унікальні (неповторні) елементи. Інтерфейс має стандартні реалізації - TreeSet , HashSet і LinkedHashSet .
• List - інтерфейс, що описує структуру даних, яка зберігає впорядковану послідовність об'єктів. Примірники, які містяться в List -і, можна вставляти та видаляти за їх індексом у даній колекції (аналог масиву, але з динамічною зміною розміру). У інтерфейсу є стандартні реалізації - ArrayList , Vector ( вважається застарілою і фактично не використовується ) і LinkedList .
• Queue - інтерфейс, що описує структуру даних, що зберігає елементи у вигляді черги, яка слідує правилу FIFO - First In First Out (першим увійшов, першим вийшов). Інтерфейс має такі стандартні реалізації: LinkedList (так, він реалізує і Queue теж) і PriotityQueue .

Друга ієрархія колекцій — Map , яка має таку структуру: У цій колекції поділів на підколекції немає (оскільки сама ієрархія Map — щось на зразок підколекції, але що лежить окремо). Стандартні реалізації Map - Hashtable (вважається застарілою), LinkedHashMap і TreeMap . Власне, коли запитують про Collection , як правило, мають на увазі обидві ієрархії.

86. Яка внутрішня будова ArrayList?

ArrayList - це аналог масиву, але зі здатністю динамічно розширюватися. Що це означає? Справа в тому, що ArrayList працює на основі звичайного масиву, а саме він зберігає елементи у внутрішньому масиві (його розмір за замовчуванням – 10 осередків). Коли внутрішній масив заповнюється, створюється новий масив, розмір якого визначається за такою формулою:

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

Тобто, якщо розмір нашого масиву 10, розмір нового буде: 10 * 3 / 2 + 1 = 16. Далі в нього копіюються всі значення з першого (старого) масиву за допомогою нативного методу 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 — у вигляді двозв'язкового списку. Це означає, кожен елемент містить посилання попередній елемент ( previous ) і наступний ( next ). У першого елемента немає посилання на попередній (адже він перший), при цьому він вважається главою списку, і в LinkedList є посилання безпосередньо на нього. Останній елемент, власне, не має наступного елемента, він є хвостом списку, і тому пряме посилання на нього є в самому LinkedList . Тому логарифмічна складність при доступі до глави або хвоста списку O(1). В ArrayListпри збільшенні списку збільшувався внутрішній масив, відразу все відбувається простіше - при додаванні елемента просто змінюються пару посилань. Давайте розглянемо деякі методи LinkedlList -а , що найбільш використовуються : 1. add(<Elelement>) — відбувається додавання в кінці списку, тобто. після останнього елемента (5) додасться посилання новий елемент як next . Новому елементу додасться посилання останній (5) як previous елемент. Логарифмічна складність такої операції буде O(1), так як необхідне лише посилання на останній елемент, а як ви пам'ятаєте, на хвіст є пряме посилання з LinkedList і логарифмічна складність доступу до нього мінімальна. 2. add(<Index>,<Elelement>)- Додавання елемента за індексом. При додаванні елемента, наприклад, в середину списку, спочатку перебираються елементи з голови та хвоста (з обох боків), доки не буде знайдено потрібне місце. Якщо ми хочемо вставити елемент між третім та четвертим (на малюнку вище), то при пошуку потрібного місця посилання next третього елемента вже вказуватиме на новий. Нове ж посилання previous буде вказувати на третій. Відповідно, посилання четвертого елемента - previous - вказуватиме вже на новий елемент, а у нового елемента посилання next буде вказувати на четвертий елемент: Логарифмічна складність даного методу залежатиме від індексу, що задається новому елементу:

• якщо він буде близький до голови або хвоста, то наближатися до O(1), оскільки перебирати елементи фактично не буде потрібно;
• якщо ж близько до середини, то O(N/2) - відбуватиметься перебирання елементів з голови та хвоста одночасно, доки не буде знайдений потрібний елемент.

3. set(<Index>,<Elelement>) — записує елемент у вказану позицію у списку. Логарифмічна складність цієї операції коливатиметься від O(1) до O(N/2), знову ж таки залежно від того, наскільки близький елемент до голови, хвоста або середини. 4. remove(<index>) - видаляє елемент зі списку, по суті роблячи так, щоб елемент, який знаходиться перед видаленим ( previous ), посилався на елемент, що йде після видаленого ( next ). І навпаки: щоб елемент, що йде після видаленого, посилався на той, що йде перед видаленим: Вийшов процес, зворотний додавання по індексу ( add(<Index>,<Elelement>) ). Бажаючим дізнатися більше про внутрішній пристрій LinkedListпораджу прочитати ось цю статтю .

88. Яка внутрішня будова HashMap?

Мабуть, одне з найпопулярніших питань при співбесіді Java-розробника. HashMap v працює з парами ключ - значення . Як же вони зберігаються всередині самого HashMapv ? Усередині HashMap є масив нод:

Node<K,V>[] table

За умовчанням розмір масиву - 16, і він збільшується щоразу вдвічі в міру заповнення елементами (при досягненні LOAD_FACTOR - певного відсотка заповненості, за умовчанням він - 0.75 ). Кожна з нод зберігає в собі хеш ключа, ключ, значення, посилання на наступний елемент: Власне, "посилання на наступний елемент" означає, що ми маємо справу з списком, де кожен елемент містить посилання на наступний елемент. Тобто HashMap зберігає дані в масиві списків. Але відразу зазначу: коли один осередок масиву table має посилання на подібний список, що складається з більш ніж одного елемента, це не є добре. Таке явище називається колізія. Але про все по порядку. Давайте розберемося, як відбувається збереження нової пари через метод put . Спочатку береться ключ hachCode() . Тому для коректної роботи hashmap як ключі потрібно брати класи, в яких даний метод перевизначено. Далі цей хеш-код використовується у внутрішньому методі — hash() — для визначення числа в межах розміру масиву table . Далі по отриманому числу йде звернення до конкретної осередку масиву table . Тут у нас два випадки:

1. Осередок порожній — у ньому зберігається нове значення Node .
2. Осередок не порожній — порівнюється значення ключів. Якщо вони рівні, нове значення Node перезаписує старе, якщо не рівні - йде звернення до елемента next (наступного), йде порівняння вже з його ключем ... І так доти, поки нове значення не перезапише деяке старе або не досягне кінця однозв'язкового списку збережеться там останнім елементом.

При пошуку елемента за ключом (метод get(<key>) ), обчислюється hashCode ключа, потім його значення в межах масиву за допомогою hash() , і по отриманому числу знаходиться осередок масиву table , в якому вже ведеться пошук шляхом перебору нід та порівняння ключа шуканої ноди із ключем поточної. Операції у Mapпри ідеальному розкладі мають алгоритмічну складність O(1), адже йде звернення до масиву, а як ви пам'ятаєте, незалежно від кількості елементів операції масив мають складність O(1). Але це в ідеальному випадку. Коли осередок масиву не порожній (2) і там вже є деякі ноди, алгоритмічна складність перетворюється на лінійну O(N), адже тепер необхідно перебрати елементи, перш ніж знайдеться потрібне місце. Не можу не згадати ось що: починаючи з Java 8, якщо у однозв'язкового списку node більше 8 елементів (колізії), він перетворюється на двійкове дерево. У такому разі алгоритмічна складність буде вже не O(N), а O(log(N)) — це вже інша річ, чи не так? HashMap— велика тема і по ній люблять ставити запитання на співбесідах. Тому раджу докладно розібратися у ній (щоб аж від зубів відсякувало). Особисто у мене не було співбесід без питань щодо HashMap . Глибокий розбір HashMap ви можете знайти у цій статті . На цьому сьогодні все, продовження...