Колекції Java (Java Collections Framework), Практична Java
Колекції або контейнери – це класи, які дозволяють зберігати та здійснювати операції над безліччю об'єктів. Колекції використовуються для збереження, отримання, маніпулювання даними та забезпечують агрегацію одних об'єктів іншими.
У цій статті будуть розглянуті основні класи та інтерфейси Collections Framework у однозадачному середовищі. Тобто. в ній не будуть розглянуті питання синхронізації колекцій та колекції, спеціально створені для роботи в багатозадачному середовищі, які знаходяться в пакеті java.util.concurrent.* .
Інтерфейси
Інтерфейси Collections Framework відіграють ключову роль. Усі класи колекцій реалізують різноманітні інтерфейси, що визначають поведінку колекції. Іншими словами,інтерфейс визначає «що робить колекція», аконкретна реалізація - «як колекція робить те, що визначає інтерфейс».
При розробці програм рекомендується, там, де це можливо, використовувати інтерфейси. Така організація дозволяє легко замінювати реалізацію інтерфейсу з метою підвищення продуктивності, наприклад. А також дозволяє розробнику сконцентруватися на задачі, а не на особливостях реалізації.
Як не важко здогадатися, перше завдання, яке постає перед розробником при використанні Collections Framework - це вибір інтерфейсу. До вибору інтерфейсу слід підходити з предметної області. Наприклад, якщо у реальному світі Ви маєте справу з чергою на обслуговування, можливо, що Вам необхідно використовувати інтерфейс java.util.Queue .
Розглянемо інтерфейси докладніше:
Інтерфейс java.lang.Iterable вказує на те, що колекція, що реалізує його, може формувати об'єкт-ітератор 1 , що реалізує інтерфейс java.util.Iterator , а значитьможе бути використана в конструкції for (у вигляді for-each) 2 .
Це є базовий інтерфейс Collections Framework. В інтерфейсі java.util.Collection визначено основні методи для маніпуляції з даними, такі як вставка (add, addAll), видалення (remove, removeAll, clear), пошук (contains). Однак, у конкретній реалізації частина методів може бути не визначена, а їх використання в цьому випадку викликає виняток java.lang.UnsupportedOperationException . Тому я рекомендував би використовувати інтерфейс більш адекватно описує предметну область.
Інтерфейси, що успадковують java.util.Collection
Інтерфейс java.util.List служить для опису списків. Цей інтерфейс визначає поведінку колекцій, які служать для зберіганняупорядкованогонабору об'єктів. Порядок, в якому зберігаються елементи, визначається порядком їх додавання до списку. Колекції, що реалізують інтерфейс java.util.List можуть зберігати 1,2 і більше копій того самого об'єкта (посилання на об'єкт). Визначено операцію отримання частини списку. А в класі java.util.Collections визначено статичний метод сортування списків.
Реалізує FIFO-буфер. Дозволяє додавати та отримувати об'єкти. При цьому об'єкти можуть бути отримані в порядку, в якому вони були додані.
Успадковує java.util.Queue. Двоспрямована черга. Дозволяє додавати та видаляти об'єкти з двох кінців. Так само може бути використаний як стек.
Колекції, що успадковують інтерфейс java.util.Set забезпечують унікальність об'єктів, що зберігаються. Іншими словами, один і той же об'єкт не може бути доданий більше одного разу. З використанням даного інтерфейсу вкрай бажано перевизначити метод equals збережених об'єктів, т.к. він використовується визначення унікальності об'єктів 3 .
Успадковує java.util.Set. Реалізації цього інтерфейсу, крім того що стежать за унікальністю об'єктів, що зберігаються, підтримують їх у порядку зростання. Відношення порядку між об'єктами може бути визначене як за допомогою методу compareTo інтерфейсу java.lang.Comparable , так і за допомогою спеціального класу-компаратора, що успадковує інтерфейс java.util.Comparator .
Відображення
Інтерфейс java.util.Map використовується для відображення кожного елемента з одного безлічі об'єктів (ключів) на інше (значення). При цьому, кожному елементу з множини ключів ставиться у відповідність рівно 1 елемент з множини значень. У той же час одному елементу з множини значень може відповідати 1, 2 і більше елементів з множини ключів. Інтерфейс java.util.Map визначає функціональність асоціативних масивів.
Успадковує java.util.Map. Реалізації цього інтерфейсу забезпечують зберігання елементів множини ключів у порядку зростання (див. java.util.SortedSet).
Реалізації
Як видно, Collections Framework забезпечує багатий вибір інтерфейсів практично на будь-який випадок. Однак ці інтерфейси лише опис того що клас колекції повинен робити. Інтерфейси не говорять про те, як той чи інший клас колекції реалізує свій інтерфейс. Понад те, різні реалізації можуть накладати додаткові обмеження.
Загальні питання зберігання даних
Спочатку розберемося яким чином класи Collections Framework зберігають дані. Якщо ви подивіться на список реалізацій інтерфейсу java.util.List , наприклад, побачите десять його реалізацій 4 . Виникає резонне питання: невже існує десять способів зберігання списків? Зовсім ні. Усі способи зберігання даних у Collections Framework можна звести трьом основним: масиви, пов'язанісписки, бінарні дерева. Розглянемо їх докладніше.
Пов'язані списки є ланцюжок з об'єктів посилаються один на одного. Розглянь ланку 6 такого ланцюжка з реалізації java.util.LinkedList:
Як видно, одна ланка містить посилання на попередню та наступну ланки, а також на об'єкт, що зберігається у списку. Реалізація java.util.LinkedList є замкнутим двонаправленим списком. Швидкість доступу до довільного елемента залежатиме від його положення щодо голови списку (тої ланки, на яку посилається об'єкт java.util.LinkedList ) і в середньому буде пропорційна розміру списку. Однак швидкість послідовного доступу до всіх елементів списку за допомогою ітератора не залежатиме від положення елементів у списку. Звідси можна зробити висновок, щоконтейнери на основі зв'язаних списків не варто використовувати там, де необхідно часто звертатися до довільного елемента.
Контейнери на основі зв'язаних списків: java.util.LinkedList.
Бінарні дерева служать для зберігання та пошуку впорядкованих об'єктів. Це означає, що для об'єктів, що зберігаються, необхідно визначити відношення порядку за допомогою методу compareTo і успадкування від інтерфейсу java.lang.Comparable або класу реалізує інтерфейс java.util.Comparator . Швидкість доступу до довільного об'єкта в деревах пропорційна логарифму розміру контейнера.
Контейнери на основі бінарних дерев: java.util.TreeSet, TreeMap.
Хеш-таблиці - контейнери на основі масивів, в яких для пошуку елемента в масиві використовується не індекс елемента в масиві, а його хеш-функція. Як відомо, для будь-якого об'єкта Java реалізована хеш-функція і рекомендується перевизначати її завжди, а для об'єктів-сутностей в обов'язковому порядку. У хеш-таблицяхіндекс визначається з урахуванням хеш-функції, а потрібної позиції масиву зберігається покажчик на пов'язаний список елементів які хеш-функції збігаються. Як не важко здогадатися, швидкість доступу буде меншою тоді, коли пов'язані списки хеш-таблиці будуть якомога коротшими, іншими словами, коли хеш-функції різних об'єктів не збігатимуться.