Довідник по Java Collections Framework

Ця публікація не є повним розбором або аналізом (не покриває пакет
java.util.concurrent
). Це, швидше, довідник, який допоможе початківцям розробникам зрозуміти ключові відмінності одних колекцій від інших, а більш досвідченим розробникам просто освіжити матеріал у пам'яті.

Що таке Java Collections Framework?

Java Collection Framework — ієрархія інтерфейсів та їх реалізацій, яка є частиною JDK та дозволяє розробнику користуватися великим количесвом структур даних з «коробки».

Базові поняття

На вершині ієрархії Java Collection Framework розташовуються 2 інтерфейсу:
Collection
та
Map
. Ці інтерфейси поділяють усі колекції, які входять до фреймворк на дві частини за типом зберігання даних: прості набори елементів і пар «ключ — значення» (словники).

image

Collection — цей інтерфейс знаходиться в складі JDK c версії 1.2 і визначає основні методи роботи з простими наборами елементів, які будуть спільними для всіх його реалізацій (наприклад
size()
,
isEmpty()
,
add(E)
та ін). Інтерфейс був злегка доопрацьований з приходом дженериків в Java 1.5. Так само у версії Java 8 було додано кілька нових методу для роботи з лямбдами (такі як
stream()
,
parallelStream()
,
removeIf(Predicate<? super E> filter)
та ін).

Важливо також зазначити, що ці медоды були реалізовані безпосередньо в інтерфейсі
default
-медоды.

Map. Цей інтерфейс також знаходиться в складі JDK c версії 1.2 і надає розробникові базові методи для роботи з даними виду «ключ — значення».також як і
Collection
, він був доповнений дженериками у версії Java 1.5 і у версії Java 8 з'явилися додаткові методи для роботи з лямбдами, а також методи, які найчастіше реалізувалися у логікою програми (
getOrDefault(Object key, V defaultValue)
,
putIfAbsent(K key, V value)
).

Інтерфейс Map [doc]



Hashtable — реалізація такої структури даних, як хеш-таблиця. Вона не дозволяє використовувати
null
в якості значення або ключа. Ця колекція була реалізована раніше, ніж Java Collection Framework, але надалі була включена до її складу. Як і інші колекції з Java 1.0,
Hashtable
є синхронізованою (майже всі методи позначені як
synchronized
). З-за цієї особливості у неї є істотні проблеми з продуктивністю і, починаючи з Java 1.2, в більшості випадків рекомендується використовувати інші реалізації інтерфейсу
Map
через відсутність у них синхронізації.

HashMap — колекція є альтернативою
Hashtable
. Двома основними відмінностями від
Hashtable
є те, що
HashMap
не синхронізована і
HashMap
дозволяє використовувати
null
в якості ключа, так і значення. Так само як і
Hashtable
, ця колекція не є впорядкованою: порядок зберігання елементів залежить від хеш-функції. Додавання елемента виконується за константна час O(1), але час видалення, отримання залежить від розподілу хеш-функції. В ідеалі є константным, але може бути і лінійним O(n). Більш детальну інформацію про
HashMap
можна почитати тут.

LinkedHashMap — це упорядкована реалізація хеш-таблиці. Тут, на відміну від
HashMap
, порядок итерирования дорівнює порядку додавання елементів. Дана особливість досягається завдяки двонаправленим зв'язків між елементами (аналогічно
LinkedList
). Але ця перевага має і недолік — збільшення пам'яті, яку займає колекція. Більш детальна інформація викладена в цій статті.

TreeMap — реалізація
Map
заснована на червоно-чорних деревах. Як і
LinkedHashMap
є впорядкованою. За замовчуванням, колекція сортується по ключам з використанням принципу "natural ordering", але це поведінка може бути налаштована під конкретну задачу за допомогою об'єкта
Comparator
, які вказується в якості параметра при створенні об'єкта
TreeMap
.

WeakHashMap — реалізація хеш-таблиці, яка організована з використанням weak references. Іншими словами, Garbage Collector автоматично видалить колекцією при наступній збірці сміття, якщо на ключ цього элеметна немає жорстких посилань.

Інтерфейс List [doc]



Реалізації цього інтерфейсу являють собою впорядковані колекції. Крім того, розробникам надається можливість доступу до елементів колекції за індексом і за значенням (так як реалізації дозволяють зберігати дублікати, результатом пошуку за значенням буде перше знайдене входження).

Vector — реалізація динамічного масиву об'єктів. Дозволяє зберігати будь-які дані, включаючи null в якості елемента.
Vector
з'явився у версії JDK Java 1.0, але як і
Hashtable
, цю колекцію не рекомендується використовувати, якщо не потрібна досягнення потокобезопасности. Тому як в
Vector
, на відміну від інших реалізацій
List
, всі операції з даними є синхронізованими. В якості альтернативи часто застосовується аналог —
ArrayList
.

Stack — ця колекція є розширенням колекції
Vector
. Була додана в Java 1.0 як реалізація стека LIFO (last-in-first-out). Є частково синхронізованою колекцією (крім методу додавання
push()
). Після додавання в Java 1.6 інтерфейсу
Deque
, рекомендується використовувати саме реалізації цього інтерфейсу, наприклад
ArrayDeque
.

ArrayList — як і
Vector 
є реалізацією динамічного масиву об'єктів. Дозволяє зберігати будь-які дані, включаючи null в якості елемента. Як можна здогадатися з назви, його реалізація заснована на звичайному масиві. Дану реалізацію слід застосовувати, якщо в процесі роботи з колекцією предплагается часте звертання до елементів за індексом. Із-за особливостей реалізації поиндексное звернення до елементів виконується за константна час O(1). Але дану колекцію рекомендується уникати, якщо потрібно честое видалення/додавання елементів в середину колекції. Детальний аналіз та опис можна почитати в це хабратопике.

LinkedList — ще одина реалізація
List
. Дозволяє зберігати будь-які дані, включаючи
null
. Особливістю реалізації даної колекції є те, що в її основі лежить двонаправлений зв'язний список (кожен елемент має посилання на попередній і наступний). Завдяки цьому, додавання і видалення з середини, доступ по індексу, значення відбувається за лінійний час O(n), а з початку і кінця за константна O(1). Так само, зважаючи реалізації, цю колекцію можна використовувати як стек або чергу. Для цього в ній реалізовані відповідні методи. На Хабре також є стаття з докладним аналізом і описом цієї колекції.

Інтерфейс Set [doc]



Являє собою неупорядковану колекцію, яка не може містити повторювані дані. Є програмною моделлю математичного поняття «множина».

HashSet — реалізація інтерфейсу
Set
, що базується на
HashTable
. Всередині використовує об'єкт HashMap для зберігання даних. В якості ключа використовується цей елемент, а значення — об'єкт-пустушка (new Object()). Із-за особливостей реалізації порядок елементів не гарантується при додаванні.

LinkedHashSet — відрізняється від
HashSet
тільки тим, що в основі лежить
LinkedHashSet
замість
HashSet
. Завдяки цьому відмінності порядок елементів при обході колекції є ідентичним порядку додавання елементів.

TreeSet — аналогічно іншим класам-реалізацій інтерфейсу
Set
містить в собі об'єкт
NavigableMap
, що і обумовлює його поведінку. Надає можливість керувати порядком елементів в колекції за допомогою об'єкта
Comparator
, або зберігає елементи з використанням "natural ordering".

Інтерфейс Queue [doc]



Цей інтерфейс описує колекції з визначеним способом вставки і вилучення елементів, а саме — черги FIFO (first-in-first-out). Крім метотов, визначених в інтерфейсу Collection, визначає додаткові методи для вилучення і додавання елементів в чергу. Більшість реалізацій даного інтерфейсу знаходиться в пакеті
java.util.concurrent
і докладно розглядаються в даному огляді.

PriorityQueue — є єдиною прямою реалізацією інтерфейсу
Queue
(була додана, як і інтерфейс Queue, в Java 1.5), не рахуючи класу
LinkedList
, який так само реалізує цей інтерфейс, але був реалізований набагато раніше. Особливістю даної черги є можливість керування порядком елементів. За замовчуванням, сортуються елементи з використанням «natural ordering», але це поведінка може бути перевизначено за допомогою об'єкта
Comparator
, який задається при створенні черги. Ця колекція не підтримує
null
в якості елементів.

ArrayDeque — реалізація інтерфейсу Deque, який розширює інтерфейс
Queue
методами, що дозволяють реалізувати конструкцію виду LIFO (last-in-first-out). Інтерфейс
Deque 
та реалізація
ArrayDeque 
були додані в Java 1.6. Ця колекція являє собою реалізацію з використанням масивів, подібно
ArrayList
, але не дозволяє звертатися до елементів за індексом і зберігання
null
. Як заявлено в документації, колекція працює швидше ніж
Stack
, якщо використовується як LIFO колекція, а також швидше ніж LinkedList, якщо використовується як FIFO.

Висновок

Java Collections Framework містить велику кількість різних структур даних, доступних в JDK «з коробки», які в більшості випадків покривають всі потреби при реалізації логіки програми. При необхідності, розробник може створити власну реалізацію, розширивши або якщо перевизначити існуючу логіку, або створивши свою власну реалізацію відповідного інтерфейсу з нуля. Також існує деяка кількість готових рішень, які є альтернативою або доповненням до Java Collections Framework. Найбільш популярними є Google Guava і Commons Collections.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.