Що можуть запитати на співбесіді: структури даних Java. Частина 2

ЧАСТИНА 1 Зараз говоримо про базу, яку має знати кожен Java developer. Про ті класичні знання, з яких все і починається. Сьогодні хотілося б торкнутися однієї з основних тем будь-якої співбесіди — структури даних у Java . Отже, замість ходіння навкруги, ми почнемо. Ловіть продовження списку питань, які можуть задати на цій темі на співбесіді.

6. Розкажіть про List

List - це інтерфейс, що представляє впорядковану структуру об'єктів, яка називається списком. "Фішка" цієї структури - те, що елементи, що містяться в List можна вставити, змінити або видалити за індексом, тобто внутрішньому ідентифікатору List . Інакше кажучи, індекс означає: «кілька елементів від початку списку». У першого елемента List індекс 0, у другого - 1, і таке інше. Таким чином, п'ятий елемент знаходиться на відстані чотирьох елементів з початку списку. Як говорилося вище, у списку важливий порядок додавання елементів. Тому структура даних і називається списком . Перерахуємо унікальні для цієї структури методи, спрямовані на роботу з елементами за індексом:

• get - повертає елемент у зазначеній позиції (за значенням індексу),
• remove — видаляє елемент у цій позиції,
• set — замінює елемент у зазначеній позиції на вказаний у методі елемент.

Основні реалізації - ArrayList і LinkedList . Докладніше про них поговоримо трохи згодом. Vector — список, орієнтований на багатопотокове використання, тому в даному класі кожен метод синхронізовано. Але врахуйте, що якщо ви хочете убезпечити деякі дії зі списками, ви синхронізуватимете цілу послідовність операцій. А синхронізація окремих операцій і менш безпечна, і набагато повільніша. Звичайно, Vector також має накладні витрати на блокування, навіть якщо вам це блокування і не потрібне. Тому зараз цей клас вважається застарілим та не використовується. До речі: ArrayList є аналогом Vector, але не використовує блокування, тому використовується повсюдно. Stack - це підклас класу Vector з одним конструктором за замовчуванням і всіма методами класу Vector , а також кількома власними (про них ми поговоримо трохи нижче). Як приклад можна уявити процес у вигляді стопки папок з документами. Нагору стопки ви кладете по одній папці, і брати ці папки можна лише у зворотному порядку, починаючи з верхньої. Власне, це і є механізм типу LIFO , тобто Last In First Out , останній прийшов – першим пішов. Стек реалізує свої методи:

• push – додає переданий елемент на вершину стека;
• peek - повертає елемент, що знаходиться на вершині стека;
• pop також повертає елемент, який знаходиться на вершині стека, але при цьому видаляє його;
• empty - перевіряє, чи порожній стек - true , чи ні - false ;
• search - Виконує пошук заданого елемента в стеку. Якщо елемент знайдено, повертається його порядковий номер щодо верхівки стека. Якщо елемент не знайдено, повертається значення -1.

В даний момент підклас Stack фактично не використовується в силу своєї простоти та негнучкості, але він може вам зустрітися. Наприклад, коли ви отримуєте деяку помилку, і в консолі бачите стек повідомлень про неї. Докладніше про стеку та черги можна почитати ось у цій статті .

7. Розкажіть про Map

Як сказано вище, Map - це колекція, що має окрему структуру інтерфейсів та їх реалізацій. Окрема вона тому, що значення не зберігаються по одному, а в парі "ключ - значення". Основні методи Map :

• put(K key, V value) - додавання елемента в Map;
• get(Object key) - пошук значення за ключем;
• containsKey(Object key) — перевірка Map наявність даного ключа;
• containsValue(Object value) - перевірка Map на наявність цього значення;
• remove(Object key) - видалення значення за його ключем.

Як ви бачите, більшість операцій працює за допомогою ключа. Як ключі, як правило, вибираються постійні об'єкти ( immutable ). Типовий приклад даного об'єкта - String . Основні реалізації Map :

1. HashMap – призначена для зберігання значень у довільному порядку, але дозволяє швидко шукати елементи картки. Дозволяє ставити ключ ключовим словом null , але з більше разу, т.к. пари з однаковими ключами записуються поверх одне одного. Головною умовою є унікальність ключів: значення можуть повторюватися (може бути кілька null значень).
2. LinkedHashMap — аналог HashMap , який зберігає значення як додавання. Відповідно, як і LinkedList , у нього є header - голова двозв'язкового списку. При ініціалізації вказує на себе.

   Також LinkedHashMap має accessOrder , який вказує, яким чином буде здійснюватися доступ до елементів під час використання ітератора. При accessOrder false доступ буде здійснюватись у порядку вставки елементів. При значенні true елементи будуть у порядку останнього доступу (елемент, до якого було останнє звернення, буде поміщено в кінець).

3. TreeMap - це Map , яка сортує елементи за значеннями ключа. Аналог TreeSet , але для пар з орієнтуванням на значення ключів. Для завдання правил сортування TreeMap ключі повинні реалізовувати інтерфейс Comparable . В іншому випадку повинен бути Comparator , орієнтований на ключі (той, який задається в конструктор TreeMap ), TreeSet - реалізований з об'єктом TreeMap всередині, в якому, власне, і відбувається вся магія.

   Докладніше про сортування в TreeMap за допомогою червоно-чорних дерев можна почитати у статті про особливості TreeMap .

4. Hashtable - аналогічний HashMap , але не дозволяє зберігати null ні як ключі, ні як значення. Він ретельно синхронізований з погляду багатопоточності, що у свою чергу означає, що він безпечний з точки зору багатопоточності. Але дана реалізація застаріла та повільна, тому зараз ви і не зустрінете Hashtable у більш-менш нових проектах.

8. ArrayList vs LinkedList. Який краще використовувати?

Це питання, мабуть, найпопулярніше за структурами даних і несе в собі деякі підводні камені. Перш ніж відповідати на нього, дізнаємося докладніше про ці структури даних. ArrayList реалізує інтерфейс List , працює за рахунок внутрішнього масиву, який розширюється при необхідності. Коли внутрішній масив повністю заповнюється, і при цьому потрібно вставити новий елемент створюється новий масив, з розміром (oldSize * 1,5) +1. Після цього всі дані зі старого масиву копіюються в новий новий елемент, старий же буде видалений збирачем сміття . Метод addдодає елемент в останню порожню комірку масиву. Тобто, якщо у нас там вже є 3 елементи, він додасть наступний до 4-го осередку. Давайте пройдемося за продуктивністю базових методів:

• 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 , тому і володіє властивостями і способами, властивими обом структурам даних. Від 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:

• найкращий вибір, якщо найчастіша операція - пошук елемента, перезапис елемента;
• Найгірший вибір, якщо операція - вставка та видалення на початку-середині, тому що будуть проходити операції зсуву елементів праворуч.

LinkedList:

• найкращий вибір, якщо нашою частою операцією є вставка та видалення на початку-середині;
• Найгірший вибір, якщо найчастіша операція – пошук.

9. Як зберігаються елементи в HashMap?

Колекція HashMap містить у собі внутрішній масив Node [] table , комірки якого ще називають бакетами (кошиками). Node містять у собі:

• key - посилання на ключ,
• value - посилання на значення,
• hash - значення hash,
• next - посилання на наступний Node .

В одному осередку масиву table[] може бути посилання на об'єкт Node з посиланням на наступний елемент Node , а він може мати посилання на інший, і так далі ... У результаті, дані елементи Node можуть утворювати список , з елементами з посиланням на наступні. При цьому значення hash у елементів одного ланцюжка однакове. Після невеликого відступу давайте подивимося, як відбувається збереження елементів у HashMap :

1. Ключ перевіряється на рівність null . Якщо він null , то key буде збережений в комірці table[0] , тому що хеш-код для null завжди дорівнює 0.
2. Якщо ключ не null , то об'єкт key викликає метод hashcode() , який видасть його хеш-код. Цей хеш-код використовується для визначення осередку масиву, де зберігатиметься об'єкт Node.
3. Далі цей hashcode міститься у внутрішній метод hash() , який обчислює hashcode, але вже в межах розміру масиву table[] .
4. Далі, залежно від значення hash, Node міститься в конкретну комірку в масиві table [] .
5. Якщо ж комірка table[] , яка використовується для збереження поточного елемента Node не порожня, а вже має якийсь елемент, відбувається перебір елементів Node за значенням next , поки не буде досягнутий останній елемент. Тобто той, у якого поле next дорівнює null .

   Під час даного перебору порівнюються ключ об'єкта Node , що охороняється , з ключами перебираються:

   • якщо буде знайдено відповідність, то перебір закінчиться, і новий Node перезапише Node , в якому знайдено відповідність (перезапишеться тільки його поле value );
   • якщо відповідності ключів не знайдені, новий Node стане останнім у цьому списку, а попередній буде мати посилання next на нього.

Часто на співбесідах з'являється питання: що таке колізія ? Ситуацію, як у осередку масиву table[] зберігається не один елемент, а ланцюжок із двох і більше, і називається колізія . У звичайних випадках, коли в одному осередку table[] зберігається лише один елемент, доступ до елементів HashMap має константну тимчасову складність O(1) . Але коли в комірці з потрібним елементом присутній ланцюжок елементів ( колізія ), то O(n) , тому що в такому разі час прямо пропорційно залежить від кількості елементів, що перебираються.

10. Розкажіть про ітератора

У схемі з відображенням ієрархії Collection вище за інтерфейс Collection був тим, з чого починалася вся ієрархія, але на практиці все не зовсім так. 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() . Призначенням Iterator є перебір елементів. Наприклад:

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());
}

Власне цикл for-each loop і реалізований під капотом за допомогою ітератора. Докладніше про це можна почитати тут . List надає свою версію ітератора, але більш круту і наворочену - ListIterator . Цей інтерфейс розширює Iterator , і він має додаткові методы:

• hasPrevious поверне true, якщо колекції є попередній елемент, інакше — false;
• previous повертає поточний елемент та переходить до попереднього; якщо такого немає, то викидається виняток NoSuchElementException;
• add вставить переданий об'єкт перед елементом, який має бути повернутий наступним викликом next() ;
• set надає поточному елементу посилання на переданий об'єкт;
• NextIndex повертає індекс наступного елемента. Якщо цього немає, то повертається розмір списку;
• previousIndex повертає індекс попереднього елемента. Якщо такого немає, то вертається число -1.

Що ж, на цьому сьогодні у мене все. Я сподіваюся, що після прочитання цієї статті ви стали ще ближчими до заповітної мрії — стати розробником.