Практическое введение в JCF (Java Collections Framework) на примерах

от
Java
В Java предусмотрено несколько способов хранения ссылок на объекты. Встроенным типом является массив, однако, ограниченное количество объектов может не всегда подойти для вашей программы. Библиотека java.util.* содержит достаточно полный набор классов контейнеров, обладающих весьма изощрёнными возможностями. Цель данной статьи - дать основные концепции и научить применять ту, или иную реализацию при решении определённых задач.


Основные интерфейсы и их реализации

В библиотеке коллекций Java существует два базовых интерфейса:
   # Collection - определены основные методы для работы с данными
   # Map - описывает коллекцию, состоящую из пар (ключ-значение)

Интерфейс Collection реализуют интерфейсы List, Set и Queue:
   # List - пронумерованная, неупорядоченная, допускающая повторяющиеся элементы коллекция
   # Set - не упорядоченная, не допускающая повторяющихся элементов, коллекция
   # Queue - очередь, принцип FIFO

Реализации интерфейса List:
   # ArrayList - инкапсуляция массива
   # LinkedList - двусвязный список
Так как оба класса имеют совершенно разные реализации, отсюда вытекают различия, влияющие на производительность, при использовании того или иного списка:
table.png

Реализации интерфейса Set:
   # HashSet - инкапсулирует HashMap, то есть для хранения хэш-таблицу. Выигрыш из этого состоит в том, что оно обеспечивает константное время выполнения следующих методов: add, contains, remove и size (при этом не исключая большие наборы)
   # LinkedHashSet - связанный список элементов набора в порядке добавления, что позволяет организовывать упорядоченную итерацию вставки в набор
   # TreeSet - элементы упорядочены по значениям дерева. Отсюда следует, что операции add, remove и contains можно вычислить, используя формулу: time=log(number)

Реализации интерфейса Queue:
   # PriorityQueue - прямая реализация, которая упорядочивает элементы по их натуральному порядку или по собственноручно написанной реализацией Comparator, который передаём в конструктор

Реализации интерфейса Map:
   # HashMap - основан на хэш-таблицах
   # LinkedHashMap - расширяя класс HashMap, создаёт связанный список элементов в карте, расположенных в порядке добавления
   # TreeMap - объекты сохраняются в отсортированном порядке по возрастанию. Блестящий выбор для хранения больших объёмов отсортированной информации, что делает поиск значительно быстрым
   # WeakHashMap - использует слабые ссылки, отличающиеся тем, что не учитывается сборщик мусора при выявлении объектов, подлежащих удалению

Стоит сказать так же и об устаревших коллекциях:
   # Enumerator - аналог интерфейса Iterator
   # Vector - аналог класса ArrayList
   # HashTable - аналог класса HashMap
   # Stack - производный от класса Vector (принцип LIFO)
   # Dictionary - аналог Map (хоть и является абстрактным классом)
Их использование не является запрещённым, но всё же не желательно


Пример 1

Создадим склад огурцов, в который будем добавлять огурцы. Больше ничего, кроме как взятие и добавление мы использовать не будем, следовательно, для решения идеально подойдёт список, а именно ArrayList.

  1. import java.util.List;
  2. import java.util.ArrayList;
  3. import java.util.Iterator;
  4.  
  5. /**
  6.  * First example
  7.  * Warehouse Cucumbers
  8.  * @author Kalter
  9.  */
  10.  
  11. public class WarehouseCucumbersV1<E> implements Iterable<E> {
  12.  
  13.     public static void main(String[] args) {
  14.         WarehouseCucumbersV1<String> wc = new WarehouseCucumbersV1<String>(){{
  15.             //добавляем элементы на склад
  16.             add("aNNiMON");
  17.             add("HoldFast");
  18.             add("Kalter");
  19.             add("Ksakep");
  20.             add("SeTSeR");
  21.             add("web_demon");
  22.             //etc...
  23.         }};
  24.         //выводим на stdout
  25.         for (String s: wc) {
  26.             System.out.println(s);
  27.         }
  28.     }
  29.  
  30.     //наш контейнер
  31.     protected final List<E> warehouse = new ArrayList<>();
  32.  
  33.     public void add(E e) {
  34.         warehouse.add(e);
  35.     }
  36.  
  37.     public E get(int index) {
  38.         return warehouse.get(index);
  39.     }
  40.  
  41.     public int size() {
  42.         return warehouse.size();
  43.     }
  44.  
  45.     @Override
  46.     public Iterator<E> iterator() {
  47.         return new Iterator<E>() {
  48.  
  49.             private int index = 0;
  50.  
  51.             @Override
  52.             public boolean hasNext() {
  53.                 return index < warehouse.size();
  54.             }
  55.  
  56.             @Override
  57.             public E next() {
  58.                 return warehouse.get(index++);
  59.             }
  60.  
  61.             @Override
  62.             public void remove() {
  63.                 throw new UnsupportedOperationException("Не реализован");
  64.             }
  65.         };
  66.     }
  67. }

Обратите внимание, наш склад реализует интерфейс Iterable - это нужно для поддержки синтаксиса foreach.

С LinkedList код почти не изменится. Домашнее задание: заполните склад миллионом огурцов, уберите вывод и протестируйте скорость выполнения, если на складе используется контейнер:
   1. ArrayList
   2. LinkedList
Выяснить, кто сделал работу быстрее и почему.


Пример 2

Огурцовый склад растёт... Со временем мы понимаем, что допустили ошибку при использовании списка для хранения наших огурцов. Пишем новый склад, основанный на множестве.

  1. import java.util.Set;
  2. import java.util.HashSet;
  3. import java.util.Iterator;
  4. import java.util.Scanner;
  5.  
  6. /**
  7.  * Second example
  8.  * Warehouse cucumbers
  9.  * @author Kalter
  10.  */
  11.  
  12. public class WarehouseCucumbersV2<E> implements Iterable<E> {
  13.  
  14.     public static void main(String[] args) {
  15.         WarehouseCucumbersV2<String> wc = new WarehouseCucumbersV2<>();
  16.  
  17.         //заполняем склад
  18.         Scanner scan = new Scanner(System.in);
  19.         String s;
  20.         System.out.print("read\n>> ");
  21.         while (!(s=scan.nextLine()).equals("-1")) {
  22.             wc.add(s);
  23.             System.out.print(">> ");
  24.         }
  25.  
  26.         //вспоминаем, кто уничтожил статусы, цветные ники и монетки
  27.         wc.die("web_demon");
  28.  
  29.         //проверяем
  30.         System.out.println("set:");
  31.         System.out.println(wc);
  32.     }
  33.  
  34.     protected final Set<E> warehouse = new HashSet<>();
  35.  
  36.     public void add(E e) {
  37.         warehouse.add(e);
  38.     }
  39.  
  40.     public boolean contains(E e) {
  41.         return warehouse.contains(e);
  42.     }
  43.  
  44.     public void die(E e) {
  45.         Iterator<E> i = iterator();
  46.         while (i.hasNext()) {
  47.             E cucumber = i.next();
  48.             if (cucumber.equals(e)) {
  49.                 i.remove();
  50.                 break;
  51.             }
  52.         }
  53.     }
  54.  
  55.     @Override
  56.     public Iterator<E> iterator() {
  57.         return warehouse.iterator();
  58.     }
  59.  
  60.     @Override
  61.     public String toString() {
  62.         StringBuilder sb = new StringBuilder();
  63.         Iterator<E> i = iterator();
  64.         while (i.hasNext()) {
  65.             sb.append(">> " + i.next().toString() + '\n');
  66.         }
  67.         return sb.toString();
  68.     }
  69. }

Домашнее задание: убрать поиск и вывод, заполнить склад миллионом огурцов и протестировать скорость выполнения, если на складе использовать контейнер:
   1. HashSet
   2. LinkedHashSet
   3. TreeSet
Выяснить, кто сделал работу быстрее и почему.


Пример 3

Выделим под каждый огурчик собственный класс и добавим их в очередь. Потом эту очередь можно передать куда-нибудь, например, на раздачу банов... Всё честно, всё по правилам.

  1. import java.util.Queue;
  2. import java.util.PriorityQueue;
  3. import java.util.Scanner;
  4.  
  5. /**
  6.  * Third example
  7.  * Cucumbers...
  8.  * @author Kalter
  9.  */
  10.  
  11. public class Example3 {
  12.  
  13.     public static void main(String[] args) {
  14.         Scanner scan = new Scanner(System.in);
  15.         Queue<Cucumber> cucumber = new PriorityQueue<>();
  16.  
  17.         //заполняем очередь
  18.         System.out.println("next (1/-1)?");
  19.         String s;
  20.         while (!(s = scan.nextLine()).equals("-1")) {
  21.             System.out.print("name: ");
  22.             String name = scan.nextLine();
  23.             System.out.print("age: ");
  24.             int age = Integer.parseInt(scan.nextLine());
  25.             cucumber.offer(new Cucumber(name,age));
  26.             System.out.println("next (1/-1)?");
  27.         }
  28.  
  29.         ban(cucumber);
  30.     }
  31.  
  32.     //раздача банов
  33.     private static void ban(Queue<Cucumber> q) {
  34.         Cucumber c;
  35.         while ((c = q.poll())!=null) {
  36.             System.out.printf("%s -> ban\n",c.getName());
  37.         }
  38.     }
  39. }
  40.  
  41. class Cucumber implements Comparable<Cucumber> {
  42.  
  43.     private String name;
  44.     private int age;
  45.  
  46.     public Cucumber(String name, int age) {
  47.         this.name = name;
  48.         this.age = age;
  49.     }
  50.  
  51.     public String getName() {
  52.         return name;
  53.     }
  54.  
  55.     public int getAge() {
  56.         return age;
  57.     }
  58.  
  59.     public void bithday() {
  60.         age++;
  61.     }
  62.  
  63.     @Override
  64.     public int compareTo(Cucumber c) {
  65.         return 0;
  66.     }
  67. }

Домашнее задание: сделать так, чтобы раздача банов происходила от старших огурцов к младшим. То есть сначала раздаём баны, тем, у кого наивысший возраст, а потом младше и младше... И так до конца.


Пример 4

У каждого огурчика есть свой код, специфичный для него и весьма сложный, понятный только ему одному (или иначе "пароль"). Напишем программу, которая для каждого огурчика будет возвращать его пароль.

  1. import java.util.Map;
  2. import java.util.TreeMap;
  3. import java.util.Scanner;
  4.  
  5. /**
  6.  * Fourth example
  7.  * Logins and passwords
  8.  * @author Kalter
  9.  */
  10.  
  11. public class Password {
  12.  
  13.     public static void main(String[] args) {
  14.  
  15.         Scanner scan = new Scanner(System.in);
  16.         Map<String,String> map = new TreeMap<>();
  17.         System.out.print("count: ");
  18.         int count = Integer.parseInt(scan.nextLine());
  19.  
  20.         //заполняем нашу карту
  21.         while (count --> 0) {
  22.             System.out.print("login: ");
  23.             String login = scan.nextLine();
  24.             System.out.print("passwords: ");
  25.             String password = scan.nextLine();
  26.             map.put(login,password);
  27.         }
  28.  
  29.         //выводим пароль, соответствующий логину из карты
  30.         String choise;
  31.         System.out.printf("finish\n\nlogin: ");
  32.         while(!(choise=scan.nextLine()).equals("-1")){
  33.             System.out.println("password: " + map.get(choise));
  34.             System.out.printf("\nlogin: ");
  35.         }
  36.     }
  37. }

Домашнее задание: объяснить, почему в качестве контейнера выбрали именно TreeSet, а не любой другой, реализующий Map. Предполагается, что огурцов очень много.


Надеюсь, эти примеры, и задания к ним вам окажутся очень полезными. Однако, встаёт такой вопрос: где же хранить огурцы? А для чего они вам нужны, там и хранить. Я думаю, для вас, после четырёх примеров выше, не составит труда определить, что и где хранить.


Нижеследующий список литературы прилагается тем, кто хочет расширить свои знания о JCF, а так же он поможет вам для понимания, приведённых мной, примеров и решения домашнего задания к каждому из них:
Глава о Контейнерах в Thinking in Java
Статья-справочник на Habrahabr
Ещё одна хорошая статья
Самые задаваемые вопросы о коллекциях и ответы на них

Контейнеры Java - необходимый инструмент. Благодаря им код, написанный вами, станет более простым, эффективным и мощным. Ниже можно скачать исходные коды всех примеров в одном архиве.

JCF.zip

  1. /*author: Kalter*/
  • +7
  • views 13555
    • Java
    Категории