Коротко про головне – Java Collections Framework

Початок шляху

Сьогодні хотілося б обговорити таку цікаву тему, як "Java Collections Framework" або, кажучи простою мовою, – колекції. Більша частина роботи коду – це обробка даних у тому чи тому вигляді. Отримати список користувачів, отримати список адрес тощо. Якось їх відсортувати, виконати пошук, зіставити. Саме тому знання колекцій вважається однією з основних навичок. Саме тому хочеться поговорити про це. Крім того, одними з найчастіших запитань на співбесідах на Java розробника є колекції. Наприклад, "намалюйте ієрархію колекцій". Допоможе нам на нашому шляху онлайн компілятор. Наприклад, можна використовувати "Tutorialspoint Online Java Compiler" або Repl.it. Шлях знайомства з будь-якими структурами даних починається зі звичайних змінних (Variables). На сайті Oracle різні теми представлені як "шляхи" або Trail. Так, шлях знайомства з Java називається Trail: Вивчення мови Java: Зміст". І основи мови (тобто Language Basics) починаються з Variables. Тому, напишемо простенький код:

public static void main(String[] args) {
	String user = "Max";
	System.out.println("Hello, " + user);
}

Він усім гарний, крім того, що ми розуміємо, що цей код гарний і красивий тільки для однієї змінної. Що робити, якщо їх кілька? Для зберігання даних одного типу придумали масиви (Arrays). У тому самому Trail від Oracle є окремий розділ, присвячений масивам. Цей розділ так і називається: "Arrays". Робота з масивами теж доволі проста:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    String[] users = new String[2];
    users[0] = "Max";
    users[1] = "John";
    System.out.println("Hello, " + Arrays.toString(users));
  }
}

Масиви вирішують проблему зі зберіганням кількох значень в одному місці. Але накладають обмеження: розмір масиву постійний. Якщо, як у прикладі, ми сказали, що розмір = 2, значить, він дорівнює двом. І все. Якщо ми хочемо більший масив – нам потрібно створити новий екземпляр. Крім того, пошук елемента – теж складна річ для масиву. Є метод Arrays.binarySearch, але цей пошук працює тільки на сортованому масиві (для несортованого масиву результат невизначений або просто непередбачуваний). Тобто пошук нас зобов'язуватиме щоразу сортувати. Видалення – теж лише очищає значення. Тому ми ще й не знаємо, скільки в масиві реально даних, знаємо тільки скільки комірок у масиві. Щоб освіжити знання про масиви

• "JavaRush: Масиви в Java"
• "The Java Tutorial: Масиви"

І як наслідок розвитку мови Java в JDK 1.2 з'явився Java Collections Framework, про який ми і будемо сьогодні говорити.

Колекція

Почати варто з самого початку. Чому колекції (Collection)? Сам термін бере свій початок з таких речей, як "Теорія типів" і "Абстрактні типи даних". Але якщо не дивитися на якісь високі матерії, то коли в нас кілька речей, то ми можемо назвати їх "колекція речей". Ті, хто збирають предмети. Взагалі саме слово колекціонувати походить від лат. collectio "збирання, збір". Тобто колекція – це збір чогось, контейнер для якихось елементів. Отже, у нас є колекція елементів. Що ми можемо захотіти з нею робити: Як видно, ми можемо захотіти досить логічні речі. А ще ми розуміємо, що ми можемо захотіти щось робити з кількома колекціями: Відповідно, для опису такої загальної поведінки для всіх колекцій написали розробники Java інтерфейс java.util.Collection. Інтерфейс Collection – це те місце, звідки беруть початок усі колекції. Collection – це ідея, це уявлення про те, як мають поводитися всі колекції. Тому, термін "Колекція" виражений у вигляді інтерфейсу. Звісно, інтерфейсу потрібні реалізації. Інтерфейс java.util.Collection має абстрактний клас AbstractCollection, тобто деяка "абстрактна колекція", яка являє собою скелет для інших реалізацій (про що написано в JavaDoc над класом java.util.AbstractCollection). Говорячи про колекції, повернімося ще раз, згадаємо, що ми хочемо ітеруватися за ними. Це означає, що ми хочемо перебирати елементи один за одним. Це дуже важлива концепція. Тому інтерфейс Collection успадковується від Iterable. Це дуже важливо, тому що, по-перше, все, що Iterable, має вміти повертати Iterator за своїм вмістом. А по-друге, все, що Iterable, може використовуватися в циклах for-each-loop. І саме за допомогою ітератора в AbstractCollection реалізовано такі методи, як contains, toArray, remove. І шлях до пізнання колекцій починається з однієї з найпоширеніших структур даних – тобто списку. Список.

Списки (List)

Отже, списки посідають важливе місце в ієрархії колекцій: Як ми бачимо, списки реалізують інтерфейс java.util.List. Списки виражають те, що у нас є колекція елементів, які розташовані в деякій послідовності один за одним. Кожен елемент має індекс (як у масиві). Здебільшого, список дозволяє мати елементи з однаковим значенням. Як ми вже сказали вище, List знає про індекс елемента. Це дає змогу отримати (get) елемент за індексом або задати значення для певного індексу (set). Методи колекцій add, addAll, remove дають змогу вказати індекс, з якого необхідно їх виконувати. Крім того, у List є своя версія ітератора, яка називається ListIterator. Цей ітератор знає про індекс елемента, тому він вміє ітеруватися не тільки вперед, а й назад. Його навіть можна створити від певного місця в колекції. Серед усіх реалізацій можна виділити дві найчастіше використовувані: ArrayList і LinkedList. По-перше, ArrayList – це список (List), що ґрунтується на масиві (Array). Це дає змогу домогтися "Довільного доступу" (Random Access) до елементів. Довільний доступ – це можливість одразу дістати елемент за індексом, а не перебирати всі елементи, поки не знайдемо елемент із потрібним індексом. Саме масив як основа дає змогу цього досягти. Навпаки, LinkedList – це пов'язаний (Linked) список (List). Кожен запис у пов'язаному списку представлений у вигляді Entry, яка зберігає самі дані, а також посилання на наступний (next) і попередній (previous) Entry. Таким чином LinkedList реалізує "Послідовний доступ"(Sequential Access). Зрозуміло, що щоб знайти 5-тий елемент, нам доведеться пройти від першого елемента до останнього, тому що у нас немає безпосередньо доступу до п'ятого елемента. Ми можемо отримати до нього доступ тільки від 4-го елемента. Різницю в їхній концепції наведено нижче: У роботі, як Ви розумієте, теж є різниця. Наприклад, додавання елементів. У LinkedList елементи просто зв'язуються, як ланки в ланцюзі. Але ось ArrayList зберігає елементи в масиві. А масив, як ми знаємо, не може змінювати свій розмір. Як же працює тоді ArrayList? А працює він дуже просто. Коли закінчується місце в масиві, то він збільшується в 1,5 рази. Ось код збільшення:

int newCapacity = oldCapacity + (oldCapacity >> 1);

Іншою відмінністю в роботі є будь-яке зміщення елементів. Наприклад, під час додавання в середину або видалення елементів. Щоб видалити з LinkedList елемент, достатньо прибрати посилання на цей елемент. У випадку ж з ArrayList ми змушені зрушувати щоразу елементи за допомогою методу System.arraycopy. Таким чином, що більше елементів, то більше дій доведеться зробити. Розглянувши ArrayList, не можна не згадати про його "попередника", про клас java.util.Vector. Відрізняється Vector від ArrayList тим, що методи для роботи з колекцією (додавання, видалення тощо) синхронізовані. Тобто якщо один потік (Thread) буде додавати елементи, то інші потоки чекатимуть, поки перший потік не закінчить свою роботу. Оскільки потокобезпека часто не потрібна, рекомендується використовувати в таких випадках клас ArrayList, про що прямим текстом сказано в JavaDoc для класу Vector. Крім того, Vector збільшує свій розмір не в 1.5 рази, як ArrayList, а в 2 рази. У решті поведінка така сама – за Vector ховається сховище елементів у вигляді масиву, і додавання/видалення елементів має ті самі наслідки, що і в ArrayList. Насправді, про Vector ми згадали не просто так. Якщо подивитися в Javadoc, то ми побачимо в "Direct Known Subclasses" таку структуру, як java.util.Stack. Стек – це цікава структура, яка є LIFO-структурою last-in-first-out (останнім прийшов, першим пішов). Стек у перекладі з англійської – стіс (як стіс книг, наприклад). Стек реалізує додаткові методи: peek (поглянути, подивитися), pop (виштовхнути), push (заштовхати). Метод peek перекладається як поглянути (наприклад, peek inside the bag перекладається як "зазирнути всередину мішка", а peek through the keyhole перекладається як "підглядати в замкову щілину"). Цей метод дає змогу подивитися "на вершину" стека, тобто отримати останній елемент, не знімаючи (тобто не видаляючи) його зі стека. Метод push заштовхує (додає) в стек новий елемент і повертає його ж, а метод pop елемент виштовхує (видаляє) і повертає видалений. У всіх трьох випадках (тобто peek, pop і push) ми працюємо тільки з останнім елементом (тобто з "верхівкою стека"). У цьому полягає основна особливість структури стек. До речі, на розуміння стеків є цікава задача, описана в книжці "Кар'єра програміста" (Cracking Coding Interview), де, використовуючи структуру "стек" (LIFO), потрібно реалізувати структуру "черга" (FIFO). Виглядатиме це так: Розбір цієї задачі можна подивитися тут: "Implement A Queue Using Stacks — The Queue ADT ("Implement Queue Using Stacks" on LeetCode)". Ось ми плавно і переходимо до нової структури даних — черги.

Черга (Queue)

Черга (Queue) – це структура, знайома нам із життя. Черги в магазини, до лікарів. Хто найперший прийшов (First In), той найперший і вийде з черги (First Out). У Java черга представлена інтерфейсом java.util.Queue. Згідно з Javadoc черги, черга додає такі методи: Як бачите, є методи-накази (їх невиконання загрожує виключенням) і є методи-прохання (неможливість їх виконати не призводить до помилок). Крім того, можна отримати елемент без видалення (peek або елемент). В інтерфейсі черги є також корисний наслідник – Deque. Це так звана "двостороння черга". Тобто така черга дає змогу використовувати цю структуру як з початку, так і з кінця. У документації сказано, що "Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.", тобто замість Stack рекомендується використовувати реалізації Deque. У Javadoc показано, які методи описує інтерфейс Deque: Давайте подивимося, які є реалізації. І побачимо цікавий факт – у стан черг "затесався" LinkedList ) Тобто LinkedList реалізує інтерфейс як List, так і Deque. Але є і "тільки черги", наприклад PriorityQueue. Про неї не часто згадують, а даремно. По-перше, у цій черзі не можна використовувати "non-comparable objects", тобто має бути або Comparator вказано, або всі об'єкти мають бути comparable. По-друге, "this implementation provides O(log(n)) time for the enqueuing and dequeuing methods". Логарифмічна складність тут не просто так. Реалізація PriorityQueue ґрунтується на "купі". У Javadoc сказано: "Priority queue represented as a balanced binary heap". Саме ж сховище для цього – звичайний масив, який росте за потреби. Коли купа невелика – у 2 рази збільшується. А потім на 50%. Коментар із коду: "Double size if small; else grow by 50%". Черга з пріоритетом і Binary Heap – окрема тема. Як реалізацію java.util.Deque можна навести клас java.util.ArrayDeque. Тобто списки можна реалізувати за допомогою пов'язаного списку і масиву і черги теж можна реалізувати за допомогою масиву або за допомогою пов'язаного списку. Інтерфейси Queue і Deque мають наслідників, які представляють "блокувальну чергу": BlockingQueue і BlockingDeque. Ось зміна інтерфейсу порівняно зі звичайними чергами: Давайте подивимося на якісь приклади блокувальних черг. А вони ж цікаві. Наприклад, BlockingQueue реалізують: PriorityBlockingQueue, SynchronousQueue, ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue. А ось BlockingDeque реалізують зі стандартного Collection Frameworks всього LinkedBlockingDeque. Кожна черга – тема окремого огляду. А в межах цього огляду зобразимо ієрархію класів не тільки з List, а й з Queue: Як ми бачимо зі схеми, інтерфейси і класи Java Collections Framework сильно переплетені. Давайте додамо ще одну гілку ієрархії – Set.

Набір

Set – перекладається як "набір". Від черги і списку Set відрізняється більшою абстракцією над зберіганням елементів. Set – як мішок із предметами, де невідомо, як лежать предмети і в якому порядку вони лягли. У Java такий набір представлений інтерфейсом java.util.Set. Як говориться в документації, Set – це "колекція, яка не містить дублікатів елементів". Цікаво, що сам інтерфейс Set не додає нових методів до інтерфейсу Collection, а лише уточнює вимоги (про те, що не має містити дублікатів). Крім того, з минулого опису випливає, що просто так із Set не можна отримати елемент. Для отримання елементів використовується Iterator. Set має ще кілька пов'язаних із собою інтерфейсів. Перший – це SortedSet. Як і випливає з назви, SortedSet вказує на те, що такий набір відсортований, а отже елементи реалізують інтерфейс Comparable або вказаний Comparator. Крім того, SortedSet пропонує кілька цікавих методів: Крім того, є методи first (найменший за значенням елемент) і last (найбільший за значенням елемент). У SortedSet є наслідник – NavigableSet. Призначення цього інтерфейсу – описати методи навігації, які є необхідними для точнішого визначення відповідних елементів. З цікавого – NavigableSet додає до звичного iterator (який йде від меншого до більшого) ітератор для зворотного порядку – descendingIterator. Крім того, NavigableSet дає змогу за допомогою методу descendingSet отримати вид на себе (View), у якому елементи йдуть у зворотному порядку. Це називається View, тому що через отриманий елемент можна змінювати елементи початкового Set. Тобто по суті це представлення початкових даних в інший спосіб, а не їхня копія. Цікаво, що NavigableSet, подібно до Queue, має pollFirst (мінімальний) і pollLast (максимальний) елементи. Тобто отримує цей елемент і прибирає з набору. Які ж є реалізації? По-перше, найвідоміша реалізація – яка ґрунтується на хеш-коді – HashSet. Інша не менш відома реалізація – яка ґрунтується на червоно-чорному дереві – TreeSet. Давайте домалюємо нашу схему: В межах колекцій залишилося розібрати ієрархію – пустельників. Яка на перший погляд стоїть осторонь – java.util.Map.

Карти (Map)

Карти – це така структура даних, у якій дані зберігаються за ключем. Наприклад, ключем може слугувати ID або код міста. І саме за цим ключем буде здійснюватися пошук даних. Цікаво, що карти винесені окремо. За словами розробників (див. "Java Collections API Design FAQ") маппінг "ключ — значення" не є колекцією. І карти можна скоріше уявити як колекцію ключів, колекцію значень, колекцію пар "ключ - значення". Ось такий цікавий звір. Які ж методи надають карти? Давайте подивимося на Java API інтерфейсу java.util.Map. Оскільки карти не є колекціями (не успадковуються від Collections), то вони не містять метод contains. І це ж логічно. Карта складається з ключів і значень. Що з цього має перевіряти метод contains і як не заплутатися? Тому інтерфейс Map має дві різні версії: containsKey (чи містить ключ) і containsValue (чи містить значення). За допомогою keySet можна отримати набір ключів (той самий Set). А за допомогою методу values можемо отримати колекцію значень у карті. Ключі в карті унікальні, що підкреслюється структурою даних Set. Значення ж можуть повторюватися, що підкреслює структура даних Collection. Крім того, за допомогою методу entrySet можемо отримати набір пар "ключ — значення". Хотілося б ще побачити, що HashMap дуже схожий на HashSet, а TreeMap на TreeSet. У них навіть схожі інтерфейси: NavigableSet і NavigableMap, SortedSet і SortedMap. Отже, наша фінальна карта матиме такий вигляд: Закінчити можна цікавим фактом, що колекція Set усередині себе використовує Map, де додані значення – це ключі, а значення скрізь однакове. Цікаво це тому, що Map не є колекцією і повертає Set, який є колекцією, але за фактом реалізований як Map. Трохи сюр, але ось так вийшло )

Висновок

Хороша новина – на цьому цей огляд закінчується. Погана новина – це дуже узагальнена стаття. Кожна реалізація кожної з колекцій заслуговує на окрему статтю, а ще на кожен прихований від наших очей алгоритм. Але мета цього огляду – згадати, які вони є і які зв'язки існують між інтерфейсами. Сподіваюся, у Вас вийде після вдумливого прочитання намалювати по пам'яті схему колекцій. Ну і за традицією трохи посилань:

• "Oracle Trail: Collections"
• "IBM Tutorial: Java Collections"
• "Java Collections: The Force Awakens by Raoul-Gabriel Urma and Richard Warburton"