Освоюємо Java/Колекції

При об’єктно орієнтованому програмуванні доводиться працювати з великою кількістю об’єктів. Зручно мати засоби групування об’єктів. Для цих цілей в Java розроблено набір інтерфейсів і класів на їх основі під назвою колекції . В основі ієрархії колекцій знаходиться інтерфейс Collection.

Структура колекцій

Згадаймо, що інтерфейс – це клас, який не містить реалізації методів, а лише їхні оголошення. Можна реалізувати безліч реалізацій інтерфейсу. Програмісту, який використовуватиме ці реалізації, достатньо знати базовий інтерфейс для роботи з його реалізаціями, тобто знати методи, які передбачає даний інтерфейс.

Collection – базовий інтерфейс, крім нього на його основі в структурі колекцій є ще декілька інтерфейсів, які розширюють базовий інтерфейс Collection. Зокрема, List, Set та SortedSet. Окремо виділяють ще інтерфейс Map. Він не походить на пряму від інтерфейсу Collection, проте його також відносять до колекцій. На їх основі створено набір класів, які згодяться програмістам для більшості випадків роботи з набором об’єктів. Тож вам не прийдеться самим їх реалізовувати.

Якщо вам цікаво, для чого стільки різних класів в колекціях? Суть в тому, що різні класи по різному реалізовують роботу з даними. Одні класи швидше здійснюють читання даних, інші вставлення і видалення, одні перевіряють, щоб не було дублювань, інші дозволяють вставляти дані за певним ключем і т.п. Доволі важливо підібрати клас, який найкраще підходить для вашого завдання і забезпечить найбільшу швидкодію. Особливо це актуально, коли кількість об’єктів величезна.

Реалізації інтерфейсу Collection

Клас ArrayList та використання ітератора

Клас ArrayList призначений для читання об'єктів по індексу. Тож не дарма у назві є слово Array (масив). Після створення колекції на основі ArrayList, прочитати дані можна кількома способами. Наступний приклад демонструє створення ArrayList, його наповнення об'єктами типу String та їх читання за допомогою методу get (int index) та за допомогою ітератора.

import java.util.ArrayList;
import java.util.ListIterator;

public class TestArrayList {

    private ArrayList<String> a1;

    public static void main(String[] args) {
        TestArrayList test = new TestArrayList();
        test.create();
        test.getData();
        test.iterateData();
    }

    void create() {
        //створюємо і наповнюємо ArrayList
        a1 = new ArrayList<String>();
        a1.add("Привіт");
        a1.add("тобі");
        a1.add("божевільний");
        a1.add("світе!");
    }

    //читаємо дані по індексу
    void getData() {
        for (int i = 0; i < a1.size(); i++) {
            System.out.print(a1.get(i) + " ");
        }
    }

    //Читаємо вміст ArrayList з допомогою ітератора 
    void iterateData() {
        ListIterator<String> it = a1.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

Результат:

Привіт тобі божевільний світе! Привіт тобі божевільний світе!

Крім вищенаведених способів можна передати вміст ArrayList у звичайний масив за допомогою методу toArray(). Якщо ви хочете детально розібратися з ArrayList і його методами, то для цього також дивіться інформацію про інтерфейси Collection, List та Iterator.

Окремо розглянемо перегляд даних з допомогою ітератора.

ListIterator<String> it=a1.listIterator();

Таким чином створюється об’єкт ітератора, посилання на який передається об'єктній змінній it типу ListIterator. ListIterator – це інтерфейс, який розширює інтерфейс Iterator декількома новими методами. Базовими ж методами інтерфейсу Iterator є ті, що використані у нас в програмі, а саме:

• boolean hasNext() – повертає true, якщо ітерація має наступний елемент
• E next() - повертає наступний елемент ітерації (буква E вказує, що це може бути елемент будь-якого типу, детальніше див. розділ Узагальнення)
• void remove() – знищує останній елемент, що повертався ітератором

Тож у коді бачимо:

while(it.hasNext()){
      System.out.print(it.next()+" "); 
}

Цикл працює поки є елементи в ітераторі. Перевірка здійснюється за допомогою методу hasNext. А вивід елементів здійснюється за допомогою методу next. Перевірка за допомогою hasNext необхідна через те, що в разі відсутності наступного елементу при виклику методу next буде викинуто виняток NoSuchElementExeption.

Інтерфейсом ListIterator передбачено ще такі методи як add, hasPrevious, next, nextIndex, previous, previousIndex, set. Назви методів говорять самі за себе. Детальніше ви можете подивитися в документації по інтерфейсу ListIterator.

Клас Itr, який реалізовує інтерфейс ListIterator є внутрішнім класом класу AbstractList. ArrayList є нащадком класу AbstractList.

Для того, щоб ітератор міг працювати з певним об’єктом, клас даного об’єкту повинен реалізовувати інтерфейс Iterable:

public interface Iterable<E>
{
   Iterator<E> iterator();
}

Інтерфейс Collection розширює даний інтерфейс.

Можна також перебрати елементи за допомогою перевантаженого з виходом java 5 циклу for (так званого “for each”):

for (String str : a1) {
     System.out.print(str+" "); 
}

При компіляції даний цикл перетворюється компілятором у цикл із ітератором.

ArrayList можна також перетворити у звичайний масив за допомогою методу toArray():

    String strArray[]= new String[a1.size()];
    strArray=a1.toArray(strArray);
    System.out.println(strArray[0]);

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

Клас LinkedList

LinkedList — це структура даних, що являє собою пов’язаний список елементів (об’єктів).

Різниця між ArrayList та LinkedList полягає в тому, що ArrayList реалізований у вигляді масиву, а LinkedList у вигляді пов’язаних між собою об’єктів. ArrayList швидко виконує читання і заміну елементів (посилань на об’єкти), проте, щоб вставити новий елемнт в середину ArrayList або видалити існуючий в середині ArrayList здійснюється послідовний зсув цілого ряду елементів масиву. В LinkedList доволі швидко відбувається вставлення нового елементу або видалення існуючого. Це відбувається тому, що в середині реалізації LinkedList змінюються лише посилання на попередній і наступний об’єкти (елементи). Проте доступ до об’єктів по індексу в LinkedList відбувається повільніше ніж в ArrayList. Тож загалом, LinkedList корисний, коли необхідно часто вставляти та видаляти елементи зі списку, а в інших випадках краще використовувати ArrayList.

Існує два конструктури LinkedList:

LinkedList()
LinkedList (Collection c)

Перший конструктор створює пустий список, а другий – створює пов’язаний список із іншої колекції.

Клас LinkedList розширює клас AbstractSequentalList та реалізує інтерфейси List, Dequeue та Queue. Реалізація останніх двох інтерфейсів (черг) означає, що ми можемо працювати із пов’язаним списком як із стеком з використанням методів pop(), push(), poll(), pollFirst(), pollLast() і т.п. Детальніше дивіться документацію по заданим інтерфейсам.

Далі попрацюємо з LinkedList, який міститиме в якості елементів об’єктні змінні типу Car.

Спочатку реалізуємо наш клас Car:

public class Car {
	private String name;
	private double price;
	private int year;
	public Car(String name, double price, int year) {
		this.name = name;
		this.price = price;
		this.year=year;
	}
	@Override
	public String toString() {
		return "\n Car [name=" + name + ", price=" + price + ", year=" + year
				+ "]";
	}
}

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

Наступний клас демонструє роботу з LinkedList:

import java.util.ArrayList;
import java.util.LinkedList;

public class TestLinkedList {

	private LinkedList<Car> ll=new LinkedList<>();
	
	public static void main(String[] args) {
		TestLinkedList t=new TestLinkedList();
		t.test();
		
	}
	void test(){
		Car car1=new Car("Ferrary", 10800, 1995);
		Car car2=new Car("Запорожець", 2600, 1989);
		ll.add(car1);
		ll.add(car2);
		//додаємо в початок списку
		ll.addFirst(new Car("Alfa Romeo 155", 11678, 2000));
		ll.remove(car2); // видалити об'єкт
		System.out.println("Після видалення car2: "+ll);
		ll.remove(1); //видалити елемент за індексом
		System.out.println("Після видалення першого елементу: "+ll);
		Car myCar=ll.get(0);
		System.out.println("Отриманий елемент за індексом [0]:"+myCar);
		ll.set(0, car1); //замінити елемент за індексом
		System.out.println("Замінений елемент за індексом [0]"+ll.get(0));
		ArrayList<Car> arrList=new ArrayList<Car>();
		arrList.add(car1);
		arrList.add(car2);
		ll.addAll(arrList); //додаємо вміст ArrayList у наш LinkedList
		System.out.println("Після додавання ArrayList:"+ll);
	}
}

Результат виконання програми:

Після видалення car2: [
 Car [name=Alfa Romeo 155, price=11678.0, year=2000], 
 Car [name=Ferrary, price=10800.0, year=1995]]
Після видалення першого елементу: [
 Car [name=Alfa Romeo 155, price=11678.0, year=2000]]
Отриманий елемент за індексом [0]:
 Car [name=Alfa Romeo 155, price=11678.0, year=2000]
Замінений елемент за індексом [0]
 Car [name=Ferrary, price=10800.0, year=1995]
Після додавання ArrayList:[
 Car [name=Ferrary, price=10800.0, year=1995], 
 Car [name=Ferrary, price=10800.0, year=1995], 
 Car [name=Запорожець, price=2600.0, year=1989]]

Перебирати елементи LinkedList також можна з допомогою ітератора та у циклі for earch.

Детальніше про методи класу дивіться документацію по класу LinkedList.

Клас HashSet

HashSet – це клас призначений для зберігання даних у вигляді множини невпорядкованих елементів. Якщо потрібна впорядкована множина, то використовуйте TreeSet. HashSet також не гарантує стабільного порядку збереження об’єктів. Тобто при додаванні об’єктів порядок зберігання елементів змінюється. Вони можуть бути збережені як в кінці множити так і в середині. Якщо потрібен один порядок зберігання об’єктів використовуйте LinkedHashSet.

Сам термін «множина» означає, що елементи не будуть повторюватися. Для зберігання і пошуку елементів використовується хеш-код об’єкта. HashSet також може містити значення null. Власне всередині самої реалізації HashSet використовується клас HashMap, який дозволяє зберігати елементи у вигляді двох складових ключа та хеш-коду. У класі HashSet хеш-код недоступний і використовується неявно для користувача.

Клас HashSet розширює клас AbstractSet та реалізує інтерфейс Set. Також реалізовує інтерфейси Serializable та Clonable. HashSet має такі конструктори:

HashSet()
HashSet (Collection  c)
HashSet (int об’єм)
HashSet (int об’єм, float коефіцієнт_заповнення)

Коефіцієнт заповнення – це число в межах 0.0 до 1.0, що представляє собою частку заповнення HashSet при якій об’єм HashSet буде збільшений. По замовчуванню в конcтрукторах, що не задають коефіцієнт заповнення, використовується значення 0.75.

Наступний приклад демонструє роботу із HashSet.

import java.util.HashSet;

public class TestHashSet {

    HashSet<String> hs=new HashSet<String>();
    public static void main(String[] args) {
        TestHashSet test=new TestHashSet();
        test.test();
    }
    void test(){
        hs.add("Австралія");
        hs.add("Україна");
        hs.add("США");
        System.out.println("1) Три країни: "+hs+" розмір="+hs.size());
        hs.add("Австралія"); // помилки не буде, але в HashSet нічого не поміняється
        System.out.println("2) Після спроби додати Авcтралію ще раз: "+hs);
        hs.remove("США"); //видаляємо США з множини
        hs.add("Німеччина");
        hs.add("Англія");
        hs.add(null);
        hs.add(null); // другий раз не додаситься
        System.out.println("3)"+hs);
        System.out.println("4) Чи містить множина Німеччину? "+hs.contains("Німеччина"));
        System.out.println("5) Множина пуста? "+hs.isEmpty());
        //можемо також отримати ітератор, або ж перебрати множину у for earch
        for (String str:hs){
        	System.out.println(str);
        	}
        hs.clear(); // очистити
        System.out.println("6) Розмір після очищення="+hs.size());
    }
}

Результат виконання:

1) Три країни: [Австралія, Україна, США] розмір=3
2) Після спроби додати Австралію ще раз: [Австралія, Україна, США]
3)[null, Австралія, Німеччина, Україна, Англія]
4) Чи містить множина Німеччину? true
5) Множина пуста? false
null
Австралія
Німеччина
Україна
Англія
6) Розмір після очищення=0

Зробити копію хеш множини можна так:

HashSet<String> hsc=(HashSet)hs.clone();

Слід зауважити, що метод clone() здійснює поверхневе (shadow) копіювання, тобто копіюються лише адреси об’єктів, які містяться у екземплярі класу HashSet, а не самі об’єкти.

При використанні ітератор може викидати виняток ConcurrentModificationException, якщо HashSet було змінено. Щоб уникнути таких випадків слід використовувати методи ітератора для зміни HashSet.

Клас HashSet несинхронізоватий для багатопоточності, проте його можна синхронізувати використовуючи метод synchronizedSet класу Collections:

Set s = Collections.synchronizedSet (new HashSet (...))

У класу String перевизначені такі методи як equal та hashcode, що дає можливість коректного порівняння їхніх хеш-кодів та значень і уникати випадків, коли будуть додаватися ідентичні рядки, незалежно від того, чи вони зберігаються в різних комірках пам’яті. Проте при використанні власних класів, на практиці для правильного функціонування HashSet (без повторення об'єктів з однаковим станом, наприклад, ідентичними полями) у класах необхідно замістити методи equals() та hashcode() самому. Так, якщо ми створимо класи оболонки, що міститимуть String поле countryName із однаковим значенням, наприклад, “Австрія”, то у нас два об'єкти вважатимуться різні, оскільки у них буде різний Хеш-код, тож вони будуть додані до HashSet. В таких випадках необхідно продумати методи equals() та hashcode().

Клас LinkedHashSet

Клас LinkedHashSet розширює клас HashSet не додаючи ніяких нових методів. Працює він дещо довше за HashSet проте зберігає порядок в якому елементи додаються до нього. Відповідно це дозволяє організувати послідовну ітерацію вставлення та витягнення елементів. Всі конструктори та методи роботи з LinkedHashSet аналогічні методам класу HashSet.

Клас TreeSet

Клас TreeSet дозволяє створювати відсортовану множину. Тобто елементи не повторюються та зберігаються у відсортованому порядку. Для зберігання елементів застосовується бінарна деревоподібна структура. Об'єкти зберігаються в відсортованому порядку по зростанню. Час доступу та одержання елементів доволі малий, тому клас TreeSet підходить для зберігання великих об’ємів відсортованих даних, які повинні бути швидко знайдені.

Клас TreeSet розширює клас AbstractSet та реалізує інтерфейс NavigableSet. NavigableSet реалізується на базі TreeMap.

В класі доступні чотири конструктори:

TreeSet () 
TreeSet(Collection  с) 
TreeSet(Comparator  компаратор) 
TreeSet(SortedSet  ss)

Третій конструктор дозволяє задавати власний компаратор, відповідно до якого буде відбуватися сортування об’єктів. Так об’єкти класу String не потребують реалізації власного компаратора, проте якщо ви хочете зберігати в класі TreeSet розроблені вами об’єкти, то потрібно задавати компаратор для цих об’єктів. Такий компаратор може реалізовувати сортування об’єктів по певному полю, наприклад по Прізвищу, якщо ваш клас зберігаю інформацію про осіб. Можна реалізувати ланцюжок компараторів з використанням методу thenComparing() класу Comparator.

TreeSet не може містити значення null. Також TreeSet не синхронізований клас, як і інші класи колекцій при потребі його потрібно синхронізувати з використанням методу Collections.synchronizedSet().

Розглянемо приклад роботи TreeSet з компаратором. Використаємо клас Car, який був попередньо використаний при роботі з LinkedList додавши лише гетер та сетер методи.

public class Car {
   private String name;
   private double price;
   private int year;
   public Car(String name, double price, int year) {
    this.name = name;
    this.price = price;
    this.year=year;
   }
   public String getName() {
    return name;
   }
   public void setName(String name) {
       this.name = name;
   }
   public double getPrice() {
       return price;
   }
   public void setPrice(double price) {
       this.price = price;
   }
   public int getYear() {
       return year;
   }
   public void setYear(int year) {
       this.year = year;
   }
   
   @Override
   public String toString() {
     return "\n Car [name=" + name + ", price=" + price + ", year=" + year+ "]";
   }

}

Клас компаратора CarsComparator виглядає так:

import java.util.Comparator;
public class CarsComparator implements Comparator { 
        @Override
        public int compare(Car car1, Car car2) {
            if(car1.getYear() > car2.getYear())
                return 1;
            else if (car1.getYear() < car2.getYear())
                return -1;
            else return 0;
        }
 
}

Наша програма з TreeSet:

import java.util.Comparator;
import java.util.TreeSet;

public class  TestTreeSet{
    CarsComparator comp=new CarsComparator();
    TreeSet<Car> ts1=new TreeSet<>(comp);
    
    public static void main(String[] args) {
        TestTreeSet t=new TestTreeSet();
        t.test();  
    }
    void test(){
     Car car1=new Car("Ferrary", 12000, 1988);
        Car car2=new Car("Ford", 13000, 1955);
        Car car3=new Car("Toyota", 13500, 2003);
        Car car4=new Car("Citroen", 12000, 2014);
        Car car5=new Car("Mercedes-Benz", 15000, 2011);
        ts1.add(car1);
        ts1.add(car2);
        ts1.add(car3);
        ts1.add(car4);
        ts1.add(car5);
        System.out.println("Сортування по роках: "+ts1);
        //Зворотній компаратор для TreeSet(Java8)
        TreeSet<Car> ts2=new TreeSet<>(comp.reversed());   
        ts2.addAll(ts1); //додати вміст попереднього TreeSet у новий
        System.out.println("Зворотнє сортування:"+ts2);
     }

}

Результат виконання:

Сортування по роках: [
 Car [name=Ford, price=13000.0, year=1955], 
 Car [name=Ferrary, price=12000.0, year=1988], 
 Car [name=Toyota, price=13500.0, year=2003], 
 Car [name=Mercedes-Benz, price=15000.0, year=2011], 
 Car [name=Citroen, price=12000.0, year=2014]]
Зворотнє сортування:[
 Car [name=Citroen, price=12000.0, year=2014], 
 Car [name=Mercedes-Benz, price=15000.0, year=2011], 
 Car [name=Toyota, price=13500.0, year=2003], 
 Car [name=Ferrary, price=12000.0, year=1988], 
 Car [name=Ford, price=13000.0, year=1955]]

Реалізація інтерфейсу NavigableSet забезпечила клас TreeSet доволі корисними методами як то ceiling(), floor(), headset(), higher(), pollFirst(), pollLast(), subset(), tailSet(), iterator(), descendingIterator(), descendingSet(). Використовуючи їх можна організувати доволі зручний вибір елементів з TreeSet. Див. детальніше документацію по TreeSet.

Клас PriorityQueue

PriorityQueue дозволяє реалізувати чергу на основі пріоритету. Така черга може бути корисна, наприклад, у разі необхідності обслуговування клієнтів згідно пріоритету. При зберіганні чисел в пріоритетній черзі, така черга гарантує, що першим елементом завжди буде найменший елемент. При цьому не гарантується ніякий стабільний послідовний порядок збереження елементів. Після додавання або видалення елементу з пріоритетної черги, порядок зберігання елементів в цій черзі змінюється таким чином, що в голові черги опиняється найменший елемент згідно його природнього порядку або згідно заданого компаратора.

PriorityQueue має наступні конструктори:
PriorityQueue()  //початковий об’єм становить 11
PriorityQueue(int  початковий_об’єм) 
PriorityQueue(Comparator comparator)
PriorityQueue(int  початковий_об'єм,  Comparator  компаратор) 
PriorityQueue(Collection  с) 
PriorityQueue(PriorityQueue  с) 
PriorityQueue(SortedSet  с)

Таким чином в разі потреби можна задати власний компаратор для видачі елементів у потрібному нам порядку.

PriorityQueue не може містити null. PriorityQueue розширює AbstractQueue та реалізує інтерфейси Serializable, Iterable, Collection, Queue.

Реалізація інтерфейсу Queue говорить нам, що в PriorityQueue доступні такі методи роботи з чергою:

• add(E e) – додати вказаний елемент у чергу
• element() – отримати, але не видаляти, елемент з голови черги
• offer(E e)- додати визначений елемент у чергу
• peek() – отримати елемент з голови черги, але не видаляти його. Повертає null, якщо черга порожня
• poll() – отримати та видалити елемент з голови черги
• remove() - отримати та видалити елемент з голови черги

Крім того в PriorityQueue достуні методи, що наявні і в інших колекціях як то: clear(), comparator(), contains(), iterator(), spliterator(), size(), toArray() тощо.

Приклад:

import java.util.PriorityQueue;

public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq= new PriorityQueue<>(11);
        pq.add(750);
        pq.add(50);
        pq.offer(1);
        pq.add(300);
        pq.add(25);
        pq.add(2);
        pq.offer(20);
        pq.add(5);
        pq.add(40);
        System.out.println("Порядок зберігання елементів"+pq);

        // Отримуємо і видаляємо елемент з голови черги 
        while (!pq.isEmpty()) {        
            System.out.println("Отримали: "+pq.poll());
            System.out.println("Новий порядок:"+pq);
        }     
    } 
}

Результат:

Порядок зберігання елементів[1, 5, 2, 25, 300, 50, 20, 750, 40]
Отримали: 1
Новий порядок:[2, 5, 20, 25, 300, 50, 40, 750]
Отримали: 2
Новий порядок:[5, 25, 20, 750, 300, 50, 40]
Отримали: 5
Новий порядок:[20, 25, 40, 750, 300, 50]
Отримали: 20
Новий порядок:[25, 50, 40, 750, 300]
Отримали: 25
Новий порядок:[40, 50, 300, 750]
Отримали: 40
Новий порядок:[50, 750, 300]
Отримали: 50
Новий порядок:[300, 750]
Отримали: 300
Новий порядок:[750]
Отримали: 750
Новий порядок:[]

Таким чином за допомогою методу poll() (його можна також замінити методом remove()), ми можемо отримувати елементи масиву у відсортованому порядку, незважаючи на те, що в самій пріоритетній черзі елементи зберігаються у іншому порядку.

Клас ArrayDeque

ArrayDeque (читається як аррейдек) – це клас який забезпечує двосторонню чергу. Іншими словами - це автоматично зростаючий масив, що дозволяє нам додавати або видаляти елементи з обох боків черги. ArrayDeque може бути використано як стек (LIFO, останній ввійшов - перший вийшов) або ж як черга (FIFO, перший ввійшов - перший вийшов).

ArrayDeque не може містити в якості елемента null.

Клас ArrayDeque швидший за клас Stack, якщо використовувати його в якості стеку і швидший за LinkedList, якщо використовувати в якості черги.

ArrayDeque розширює клас AbstractCollection та реалізує інтерфейси Deque, Cloneable, Serializable. Таким чином ми можемо використовувати для роботи з даним класом, як методи інтерфейсу Deque (який розширює інтерфейс Queue) так і методи інтерфейсу Collection.

Якщо використовується ітератор, то він буде викидати виняток ConcurrentModificationException, якщо вміст ArrayDeque був модифікований після створення ітератора. Таким чином ітератор необхідно з обережністю використовувати з ArrayDeque.

В ArrayDeque доступні наступні конструктори:

ArrayDeque() // пустий ArrayDeque з початковим об’ємом 16 елентів
ArrayDeque(Collection c) // міститиме елементи колекції в порядку, що повертає ітератор даної колекції
ArrayDeque(int numElements) // дозволяє задати початковий об’єм

При потребі збільшення об'єму, то він автоматично збільшується вдвічі.

Наступний приклад демонструє роботу із ArrayDeque у вигляді стека та у в вигляді черги:

import java.util.ArrayDeque;

public class TestArrayDeque {

    public static void main(String[] args) {
         ArrayDeque<String> ad=new ArrayDeque<>();
     
         System.out.println("Використання в якості стеку");
         ad.push("Перший"); // метод інтерфуйсу Deque
         ad.push("Другий"); 
         ad.push("Третій");
         System.out.println("Перший елемент ArrayDeque: "+ad.getFirst());//Отримуємо перший елемент, але не видаляємо
         System.out.println("Вміст ArrayDeque: "+ad);
         System.out.println(ad.pop()); //Отримуємо і видаляємо з вершини стеку
         System.out.println(ad.pop()); //еквівалентно до removeFirst()
         System.out.println(ad.pop()); 
         //System.out.println(ad.pop()); //ArrayDeque порожній видасть NoSuchElementException
         System.out.println();
         System.out.println("Використання в якості черги");
         
         ad.offer("Перший"); 
         ad.offer("Другий"); 
         ad.offer("Третій");
         System.out.println("Перший елемент ArrayDeque: "+ad.getFirst());//Отримуємо перший елемент, але не видаляємо
         System.out.println("Вміст ArrayDeque: "+ad);
         System.out.println(ad.poll()); //витягнути і видалити з голови
         System.out.println(ad.poll());
         System.out.println(ad.poll());
         System.out.println(ad.poll());
    }

}

Результат роботи:

Використання в якості стеку
Перший елемент ArrayDeque: Третій
Вміст ArrayDeque: [Третій, Другий, Перший]
Третій
Другий
Перший

Використання в якості черги
Перший елемент ArrayDeque: Перший
Вміст ArrayDeque: [Перший, Другий, Третій]
Перший
Другий
Третій
null

Дивіться також офіційну документацію по: Інтерфейсу Deque та Інтерфейсу Collection

Клас EnumSet

Клас EnumSet — це одна з спеціалізованих реалізацій інтерфейсу Set для використання з перелічуваним типом даних (enum). EnumSet розширює AbstractSet та реалізує Cloneable та Serializable інтерфейси Java. EnumSet заміщує більшість методів інтерфейсів Set та Collection. EnumSet доволі швидка реалізація Set, швидша за HashSet, тому що всередині використовуються побітові операції, а не хеш-коди об’єктів.

EnumSet не синхронізований і повинен бути синхронізований ззовні, наприклад з використанням методу Collections.synchronizedSet(java.util.Set).

Всі елементи enum множини мають походити від єдиного перелічуваного типу, що вказується, коли множина створюється явно або неявно. EnumSet не дозволяє додавати значення null. Елементи зберігаються в порядку в якому їх подано в переліченні (enum).

EnumSet використовує безвідмовний (fail-safe) ітератор, що працює з копією EnumSet, тобто ітератор не буде викидати виняток ConcurrentModificationException, в разі зміни даних множини поза ітератором.

EnumSet – це відкритий абстрактний клас, який не має відкритого конструктора, для створення об’єкту EnumSet використовуються відповідні статичні факторні методи. В даних методах для створення EnumSet використовуються дві реалізації даного класу RegularEnumSet(для зберігання невеликих перелічень, до 64) та JumboEnumSet (для зберігання великих перелічень). Наступний приклад демонструє роботу з EnumSet:

import java.util.EnumSet; 
     
enum Colors  
{ 
    RED, GREEN, YELLOW, BLUE, BLACK 
}; 
public class TestEnumSet 
{ 
    public static void main(String[] args)  
    { 
        // Створюємо множину 
        EnumSet<Colors> set1, set2, set3, set4, set5; 
  
        // Додаємо окремі елементи, порядок зберігання буде згідно порядку перелічення
        set1 = EnumSet.of(Colors.RED, Colors.GREEN,  
                          Colors.BLACK, Colors.BLUE); 
        // Заповнити тими елемнтами, яких нема у вказаній множині
        set2 = EnumSet.complementOf(set1);
        // Всі із даного перелічення
        set3 = EnumSet.allOf(Colors.class);
        // Додати усі елементи перелічення в діапазоні від GREEN до BLACK
        set4 = EnumSet.range(Colors.GREEN, Colors.BLACK); 
        // створити пусту множину перелічень відповідного типу
        set5= EnumSet.noneOf(Colors.class);
        System.out.println("Set 1: " + set1); 
        System.out.println("Set 2: " + set2); 
        System.out.println("Set 3: " + set3); 
        System.out.println("Set 4: " + set4); 
        System.out.println("Set 5: " + set5); 
    } 
}

Результат роботи:

Set 1: [RED, GREEN, BLUE, BLACK]
Set 2: [YELLOW]
Set 3: [RED, GREEN, YELLOW, BLUE, BLACK]
Set 4: [GREEN, YELLOW, BLUE, BLACK]
Set 5: []

Інтерфейс Map та класи, що його реалізують

Зіставлення (англ. map, також перекладають як відображення)– це об’єкт який зіставляє ключ із відповідним значенням (key/value). Маючи ключ ви можете знайти його значення. І ключ, і значення є об’єктами. Ключ може бути унікальним, а значення може повторюватися. Деякі зіставлення можуть приймати null ключ і null значення, інші не можуть.

Зіставлення не підтримують Iterable інтерфейс. Тому ви не зможете використати ітератор для перебору вмісту зіставлення. Також ви не можете використовувати цикл for each. Проте можна перетворити зіставлення у інший тип колекції і вже на ньому можна отримати ітератор.

Основу зіставлень складає інтерфейс Map.

Map є узагальненим (див. розділ Узагальнення) і оголошений так:

interface Map<K, V>

де K – визначає тип ключа, а V визначає тип значення.

Інтерфейс SortedMap розширює інтерфейс Map і забезпечує, що вміст зберігається в порядку зростання, базуючись на значенні ключа.

Інтерфейс NavigableMap розширює SortedMap і забезпечує повернення вмісту базуючись на схожості ключа або ключів.

Інтерфейс Map.Entry – вкладений в Map інтерфейс і забезпечує роботу із вмістом зіставлення.

Класи, що реалізують інтерфейс Map наведені в таблиці.

Клас	Опис
AbstractMap	Реалізує більшість інтерфейсу Map
EnumMap	Розширює AbstractMap для використання з перелічуваними ключами.
HashMap	HashMap розширює AbstractMap, щоб використовувати хеш таблиці.
TreeMap	TreeMap розширює AbstractMap для використання дерев.
WeakHashMap	WeakHashMap розширює AbstractMap для використання слабких ключів, що забезпечує утилізацію невикористовуваних ключів збирачем мусору
LinkedHashMap	LinkedHashMap розширює HashMap дозволяючи ітерацію з вводом елементів в певному порядку
IdentityHashMap	IdentityHashMap розширює AbstractMap і використовує рівність посилань при порівнянні документів (для специфічних задач)

Клас HashMap

HashMap розширює AbstractMap та реалізує інтерфейс Map. Клас не додає власних методів. Клас використовує хеш таблиці для зберігання зіставлення. HashMap не гарантує порядок елементів. HashMap має наступні конструктори:

HashMap( )

HashMap(Map<? extends K, ? extends V> m)

HashMap(int capacity)

HashMap(int capacity, float fillRatio)

Перший створює HashMap по замовчуванню. Другий створює хеш зіставлення використовуючи елементи m. Третій задає ємність хеш зіставлення. Четвертий задає ємність(по замовчуванню 16) та коефіцієнт заповнення (по замовчуванню 0.75).

package Map;

import java.util.HashMap;
import java.util.*;
import java.util.Set;

public class TestHashMap {
	
	 public static void main(String[] args) {
		// створюємо об'єкт HashMap з назвою capitalCities
		HashMap<String, String> capitalCities = new HashMap<String, String>();

		// додаємо ключі і значення (Країна, Столиця)
		capitalCities.put("Англія", "Лондон");
		capitalCities.put("Німеччина", "Берлін");
		capitalCities.put("Норвегія", "Осло");
		capitalCities.put("США", "Вашингтон");
		//вивести значення об'єкту capitalCities
		System.out.println(capitalCities);
		//звернутися до HashMap використовуючи ключ
		System.out.println(" Отримати столицю США");
		System.out.println(capitalCities.get("США"));
		//Видалити Англію
		System.out.println(" Видаляємо Англію");
		capitalCities.remove("Англія");
		System.out.println(capitalCities);
		//видалити все можна так
		//capitalCities.clear();
		// друкуємо ключі
		System.out.println(" Ключі:");
		for (String i : capitalCities.keySet()) {
		  System.out.println(i);
		}
		// друкуємо значення
		System.out.println(" Значення:");		
		for (String i : capitalCities.values()) {
		  System.out.println(i);
		}
		// Друкувати ключі і значення
		System.out.println(" Ключі і значення:");
		for (String i : capitalCities.keySet()) {
		  System.out.println("key: " + i + " value: " + capitalCities.get(i));
		}
		
		System.out.println("Використовуємо Map.Entry");
		//одержати множину входжень
		Set<Map.Entry<String,String>> set=capitalCities.entrySet();
		//вивести множину входжень
		for(Map.Entry<String, String> me: set) {
			System.out.print(me.getKey()+": ");
			System.out.println(me.getValue());
		}

	 }
}

Результат:

{США=Вашингтон, Англія=Лондон, Норвегія=Осло, Німеччина=Берлін}
 Отримати столицю США
Вашингтон
 Видаляємо Англію
{США=Вашингтон, Норвегія=Осло, Німеччина=Берлін}
 Ключі:
США
Норвегія
Німеччина
 Значення:
Вашингтон
Осло
Берлін
 Ключі і значення:
key: США value: Вашингтон
key: Норвегія value: Осло
key: Німеччина value: Берлін
Використовуємо Map.Entry
США: Вашингтон
Норвегія: Осло
Німеччина: Берлін

Ключі і значення в HashMap є об’єктами. Якщо ми хочемо використати, наприклад, числа цілого типу (іnt) то використовуватиметься клас обгортка Integer. Так само і для інших примітивних типів.

Клас TreeMap

Клас TreeMap розширює AbstractMap та реалізує інтерфейс NavigableMap. TreeMap не містить методів крім тих, що визначені у NavigableMap та класі AbstractMap. Що забезпечує зберігання зіставлень за допомогою деревовидної структури. TreeMap забезпечує зберігання пар ключ/значення у відсортованому порядку (в порядку зростання), що забезпечує швидкий доступ до елементів. TreeMap по замовчуванню сортується за ключами. Для задання іншого сортування використовують компаратор.

TreeMap узагальнений клас і оголошується так:

class TreeMap<K,V>

де K – задає тип ключа, а V – задає тип значення.

TreeMap визначає наступні конструктори:

TreeMap( ) 
TreeMap(Comparator<? super K> comp)
TreeMap(Map<? extends K, ? extends V> m) 
TreeMap(SortedMap<K, ? extends V> sm)

Перший створює пусте деревовидне зіставлення, що буде відсортоване використовуючи природній порядок ключів. Другий створює пусте зіставлення, що буде відсортоване використовуючи компаратор. Третій створює деревовидне зіставлення із входжень зіставлення m, що буде відсортоване в природньому порядку. Третій ініціалізує деревовидне зіставлення входженнями із sm з порядком сортуванням того ж sm.

package Map;

import java.util.TreeMap;
import java.util.*;

public class TestTreeMap {
	public static void main(String[] args) {
		TreeMap<String, Integer> countries = new TreeMap<String, Integer>();
		countries.put("Гваделупа",1);
		countries.put("США",2);
		countries.put("Гаваї",3);
		countries.put("Бельгія", 4);
		//вивести вміст
		System.out.println(countries);
		//вивести останній ключ
		System.out.println("Останній ключ:"+countries.lastKey());
		countries.put("Албанія", 5);
		
		System.out.println(" Вміст зіставлення:");
		// взяти множину входжень
		Set<Map.Entry<String, Integer>> set = countries.entrySet();
		// Вивести елементи
		for(Map.Entry<String, Integer> me : set) {
			System.out.print(me.getKey() + ": ");
			System.out.println(me.getValue());
			}
			System.out.println();	
	}

}

Результат:

{Бельгія=4, Гаваї=3, Гваделупа=1, США=2}
Останній ключ:США
 Вміст зіставлення:
Албанія: 5
Бельгія: 4
Гаваї: 3
Гваделупа: 1
США: 2

Клас LinkedHashMap

Клас LinkedHashMap розширює HashMap і підтримує пов'язаний список записів у зіставленні, в порядку в якому вони додавались. При необхідності можна задати зіставлення в якому записи будуть зберігатись в порядку останнього доступу.

LinkedHashMap має наступні конструктори:

LinkedHashMap( ) 
LinkedHashMap(Map<? extends K, ? extends V> m) 
LinkedHashMap(int capacity) 
LinkedHashMap(int capacity, float fillRatio) 
LinkedHashMap(int capacity, float fillRatio, boolean Order)

Перший конструктор створює LinkedHashMap по замовчуванню. Другий ініціалізує LinkedHashMap елементами із зіставлення m. Третій конструктор задає ємність. Четвертий задає ємність та коефіцієнт заповнення. Ємність по замовчуванню - 16, а коефіцієнт заповнення по замовчуванню становить 0,75. Останній конструктор дозволяє задати порядок заповнення зіставлення, чи записи зберігатимуться в порядку вставлення чи в порядку останнього доступу. Якщо Order є true тоді використовуються порядок зберігання по порядку доступу, якщо false тоді використовується порядок вставлення.

LinkedHashMap додає лише один власний метод - removeEldestEntry. Якщо його замістити так, щоб він повертав true, то буде видалятися найстаріший елемент при використанні методів put() та putAll(). Таким чином можна, наприклад, встановити, щоб в зіставлення було б не більше певної кількості елементів.

var cache = new LinkedHashMap<K, V>(128, 0.75F, true)
{ 
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
  {
  return size() > 100; //якщо елементів більше ста, то старі записи видалятимуться
  }
};

(необхідно описати ще EnumMap та IdentityHashMap)

Алгоритми

В структурі колекцій існує клас Collections, який надає ряд зручних статичних методів для роботи з даними. Нагадаємо, що статичні методи – це методи, які не потребують створення об'єктів і реалізують ряд додаткових алгоритмів по роботі з колекціями, як то сортування колекцій, знаходження максимального і мінімального елементу, перемішування, копіювання і т.п.

(необхідно розширити)

Arrays

Клас Arrays надає різноманітні статичні методи, що корисні при використанні масивів.

(Необхідно доповнити)

Успадковані класи

Ранні версії Java не включали структуру Collections. Там було визначено декілька класів та інтерфейсів, що надавали методи для зберігання об'єктів. Структура Collections була додана в Java 2. (j2se 1.2). Тоді початкові класи були перероблені для підтримки інтерфейсів колекцій. Ці ранні класи також знані як успадковані класи (Legacy classes). В Java 5 успадковані класи та інтерфейси були перероблені для підтримки узагальнень. Їх підтримують, тому що до сих пір існує код, який їх використовує. Успадковані класи - синхронізовані. Класи входять в пакет java.util. Успадкованими є наступні класи:

• Dictionary
• HashTable
• Properties
• Stack
• Vector

Успадкованим є інтерфейс Enumaration, на заміну якому прийшов інтерфейс Iterator. Enumaration інтерфейс до сих пір використовується в декількох методах класів Vector та Properties.

Додаткова література

• Плешко Д.Д. Лекція VІ. Колекції. (Об'єктно-орієнтоване програмування в Java)
• Колекції в Java(англ)
• Робота з hashcode() та equals() (англ)
• Огляд структори колекцій(англ)
• Колекції Java