Коллекции*

Теоретический блок

Вам нужно просто прочитать его. Команды выполнять не требуется.

Введение

Коллекции – это набор готовых типизированных классов для работы с множеством объектов заданного класса. Т.е. классов, которые строятся на основе другого класса, переданного в параметрах, например, есть класс отвечающий за список, в зависимости от класса, который мы передадим в параметрах, этот список может быть списком целых чисел, а может вообще быть списком объектов класса, созданного нами.

Вне зависимости от класса, который мы передадим коллекции будут работать одинаково, так что изучив коллекции можно забыть о «ручных» сортировках, поисках элементов и т.д. К тому же алгоритмы оптимизированы. Но, забегая вперёд, разные структуры работают по-разному, поэтому один структуры позволяют быстро обратиться к элементу по индексу, но медленно выполняют вставку.

Поэтому, если вы хотите писать красивый и быстрый код, надо с умом подходить к выбору класса коллекции, который будет решать поставленную вами задачу.

Вообще коллекции содержат очень много классов, интерфейсов и абстрактных классов, но в рамках этого курса мы рассмотри только часть только готовых классов – «решений из коробки», с которыми можно работать, просто создав объект класса.

Обзор рассматриваемых коллекций

Для записи быстродействия алгоритма(кол-ва операций), работающего с множеством объектом принято обозначение O(f(n)), где n – это кол-во элементов в множестве, а f – зависимость кол-ва операций от n, причём принято пренебрегать константами. Т.е. если алгоритм для n элементов сделать 5n2 операций, его быстродействие можно оценить как O(n2). Если вне зависимости от кол-ва элементов алгоритм выполняется за константное кол-во операций, то его сложность обозначается O(1).

Мы рассмотрим следующие структуры (повторюсь, это лишь часть коллекций):

• ArrayList
• LinkedList
• HashMap
• HashSet
• TreeSet

Быстродействие выполнения типовых алгоритмов указанных структур показано в таблице 1.

	Временная сложность
	Индекс	Поиск	Вставка	Удаление
ArrayList	O(1)	O(n)	O(n)	O(n)
LinkedList	O(n)	O(n)	O(1)	O(1)
HashSet	-	O(1)	O(1)	O(1)
HashMap	-	O(1)	O(1)	O(1)
TreeSet	-	O(log(n))	O(log(n))	O(log(n))

мы разбираем типичные задачи для работы со структурами данных: индекс элемента по значению, поиск элемента, вставка элемента, удаление элемента. Т.к. только ArrayList и LinkedList являются аналогами массива, то у только у них определена связка элемента и его индекса.

Использование коллекций

Для того, чтобы создать объект рассматриваемых нами классов, напомним, необходимо не только указать класс коллекции, но и класс объектов, которые эта коллекция будет хранить.

Имя_коллекции<Имя_класса> имя_переменной = new Имя_коллекции<>();

Все классы коллекции позволяют перебрать элементы при помощи for-each конструкции, что упрощает и унифицирует работу с классами вне зависимости от внутренней реализации. Единственное ограничение на использование коллекции заключается в том, что коллекции не могут работать с базовыми типами, поэтому вместо примитивных типов необходимо использовать их классы-оболочки.

ArrayList

ArrayList реализует структуру, построенную на основе автоматически расширяемого массива. Создать переменную можно следующим образом:

ArrayList<Integer> lst = new ArrayList<>();
ArrayList<Integer> lst2;

Добавление элементов

Добавление элементов выполняется с помощью метода add():

ArrayList friendsList = new ArrayList();
friendsList.add("Антонов Сергей");
friendsList.add("Сергеев Антон");

При необходимости можно добавить новый элемент в указанное место (по индексу в диапазоне от 0 до size()-1 :

friendsList.add(1, "Андреев Игорь");

При добавлении и удалении элементов ArrayList меняет свой размер, который можно узнать с помощью метода `size()``.

System.out.println(friendsList.size());

Обратиться к элементу можно по его индексу с помощью метода get(). Напомним, что индексация в ArrayList, как и в статических массивах, начинается с 0.

System.out.println(friendsList.get(0));

Соответственно, обращение к последнему элементу массива будет выглядеть так:

System.out.println(friendsList.get(friendsList.size() -1));

Замена и удаление элементов

Для замены элемента в массиве нужно использовать метод `set()`` с указанием индекса и новым значением:

friendsList.set(1, "Викторов Андрей");

Для удаления элемента из массива пользуются методом `remove()``. При этом элемент можно удалять как по индексу, так и по объекту:

friendsList.remove("Антонов Сергей");
friendsList.remove(0);

Очистка списка (удаление всех элементов) - это метод clear()

friendsList.clear();

При поиске элемента в массиве применяют indexOf(), который возвращает номер элемента в диапазоне от 0 до size()-1, или отрицательное число, если элемент не найден.

int ind = friendsList.indexOf("Сергеев Антон");
System. out.println("Индекс элемента = " + ind);

Просмотр и поиск элементов

Просмотр всего списка можно осуществить несколькими способами:

а) через цикл for

for (int i = 0; i < friendsList.size(); i++) {
    System. out.println(friendsList.get(i));
}

б) через цикл for each

for (String friend : friendsList) {
    System. out.println(friend);
}

в) через Iterator

Интерфейс Iterator (итератор) содержит обобщенную схему доступа ко всем элементам контейнера (коллекции объектов), которая не зависит от особенностей его организации. Итератор последовательности возвращает элементы в соответствии с линейным порядком их следования.

Основными методами Iterator являются:

• hasNext() - возвращает true, если следующий элемент существует в коллекции;
• next() - возвращает следующий элемент коллекции, при этом итератор переходит на следующий элемент;

Iterator iterator = friendsList.iterator();
while (iterator.hasNext()) {
    System. out.println(iterator.next());
}

Чтобы узнать, есть в массиве какой-либо элемент, можно воспользоваться методом contains(), который вернёт true или false:

if (friendsList.contains("John Johnson")) {
    System. out.println("Есть такой друг!");
}

В массиве ArrayList значения вполне могут совпадать (как и в обычном статическом массиве).

ArrayList<String> friendsList = new ArrayList<String>();
friendsList.add("Иванов");
friendsList.add("Петров");
friendsList.add("Сидоров");
friendsList.add("Иванов");
int count = Collections. frequency(friendsList, "Иванов");
System. out.println(count + " ");

Подробнее класс Arrays мы рассмотрим позже.

LinkedList

LinkedList содержит почти все те же методы, что и ArrayList, но реализован на основе связанного списка, а не массива, поэтому снова разбирать те же методы не имеет смысла. Напомним только, что LinkedList и ArrayList выполняют операции с разной скоростью, поэтому в зависимости от стоящей задачи, надо думать, какую коллекцию использовать.

HashSet

HashSet – это множество уникальных элементов, основанное на хэш-кодах. Что такое хэш-коды, в рамках данного курса мы рассматривать не будем. Рассмотри только основные методы:

• public int size() – размер множества
• public boolean isEmpty() – пустое ли множество
• public boolean contains(Object o) – проверка, содержит ли множество заданный объект
• public boolean add(Object o) – добавить объект в множество
• public Object[] toArray() – преобразование к массиву
• public boolean remove(Object o) – удалить объект
• public boolean retainAll(Collection c) - (retain - сохранить) Выполняет операцию "пересечение множеств". Т.е. есть ли совпадающие объекты в множествах
• public void clear() – очистить множество

HashSet<Integer> set = new HashSet<>();
HashSet<Integer> set2 = new HashSet<>();
System.out.println(set2.isEmpty());
set.add(1);
set.add(2);
set.add(3);
set.add(4);
set2.add(1);
set2.add(-1);
set2.add(2);
set2.add(-2);
System.out.println(set);
System.out.println(set2);
System.out.println(set2.isEmpty());
System.out.println(set.size());
set.add(1);
System.out.println(set.size());
System.out.println(set.contains(2)+" "+set2.contains(4));
set.remove(2);
System.out.println(set);
System.out.println(set.retainAll(set2));
set.clear();
System.out.println(set);

На консоль будет выведено:

true
[1, 2, 3, 4]
[-1, 1, -2, 2]
false
4
4
true false
[1, 3, 4]
true
[]

HashMap

HashMap – это ассоциативный массив, т.е. массив, к элементам которого можно обращаться не по индексу, а по объекту заданного класса. Иными словами, HashMap хранит пары ключ-значение. Для того, чтобы разобраться в работе HashMap, надо разобраться с отображения. Отображения представляют такие наборы, в которых каждый объект представляет пару "ключ-значение". Такие коллекции облегчают поиск элемента, если нам известен ключ - уникальный идентификатор объекта. В java отобржение реализует класс Map.Entry<K, V>.

Разберём основные методы HashMap:

• void clear() - очищает коллекцию
• boolean containsKey(Object k) - возвращает true, если коллекция содержит ключ k
• boolean containsValue(Object v) - возвращает true, если коллекция содержит значение v
• Set<Map.Entry<K, V>> entrySet() - возвращает набор элементов коллекции. Все элементы представляют объект Map.Entry
• boolean equals(Object obj) - возвращает true, если коллекция идентична коллекции, передаваемой через параметр obj
• boolean isEmpty - возвращает true, если коллекция пуста
• V get(Object k) - возвращает значение объекта, ключ которого равен k. Если такого элемента не окажется, то возвращается значение null
• V put(K k, V v) - помещает в коллекцию новый объект с ключом k и значением v. Если в коллекции уже есть объект с подобным ключом, то он перезаписывается. После добавления возвращает предыдущее значение для ключа k, если он уже был в коллекции. Если же ключа еще не было в коллекции, то возвращается значение null
• Set<K> keySet() - возвращает набор всех ключей отображения
• V remove(Object k) - удаляет объект с ключом k
• int size() - возвращает количество элементов коллекции

Чтобы положить объект в коллекцию, используется метод put, а чтобы получить по ключу - метод get. Реализация интерфейса Map также позволяет получить наборы как ключей, так и значений. А метод entrySet() возвращает набор всех элементов в виде объектов Map.Entry<K, V>.

Обобщенный интерфейс Map.Entry<K, V> представляет объект с ключом типа K и значением типа V и определяет следующие методы:

• boolean equals(Object obj) - возвращает true, если объект obj, представляющий интерфейс Map.Entry, идентичен текущему
• K getKey() - возвращает ключ объекта отображения
• V getValue() - возвращает значение объекта отображения
• Set<K> keySet() - возвращает набор всех ключей отображения
• V setValue(V v) - устанавливает для текущего объекта значение v

При переборе объектов отображения мы будем оперировать этими методами для работы с ключами и значениями объектов.

Пример использования класса:

public class Main {

    public static void main(String[] args) {
        HashMap<Integer, String> states = new HashMap<Integer, String>();
        states.put(1, "Германия");
        states.put(2, "Испания");
        states.put(4, "Франция");
        states.put(3, "Италия");

        // получим объект по ключу 2
        String first = states.get(2);
        System.out.println(first);
        // получим весь набор ключей
        Set<Integer> keys = states.keySet();
        // получить набор всех значений
        Collection<String> values = states.values();
        //заменить элемент
        states.replace(1, "Бельгия");
        // удаление элемента по ключу 2
        states.remove(2);
        // перебор элементов
        for(Map.Entry<Integer, String> item : states.entrySet()){

            System.out.printf("Ключ: %d  Значение: %s \n", item.getKey(), item.getValue());
        }

        Map<String, Person> people = new HashMap<String, Person>();
        people.put("1240i54", new Person("Tom"));
        people.put("1564i55", new Person("Bill"));
        people.put("4540i56", new Person("Nick"));

        for(Map.Entry<String, Person> item : people.entrySet()){
            System.out.printf("Ключ: %s  Значение: %s \n", item.getKey(), item.getValue().getName());
        }

    }

    static class Person{

        private String name;
        public Person(String value){

            name=value;
        }
        String getName(){return name;}
    }
}

На консоль будет выведено:

Испания
Ключ: 1  Значение: Бельгия
Ключ: 3  Значение: Италия
Ключ: 4  Значение: Франция
Ключ: 1564i55  Значение: Bill
Ключ: 4540i56  Значение: Nick
Ключ: 1240i54  Значение: Tom

Treeset

Обобщенный класс TreeSet<E> представляет структуру данных в виде дерева, в котором все объекты хранятся в отсортированном виде по возрастанию. В классе TreeSet определены следующие конструкторы:

Использование TreeSet не сильно отличается, особый интерес в TreeSet представляют методы TreeSet<E> headSet(Object o) и TreeSet<E> tailSet(Object o), возвращающие соответственно новое дерево, содержащее все элементы, большие переданного и меньшие переданного соответственно. Также довольно полезен метод TreeSet<E> headSet(Object o1,Object o2), возвращающий дерево, состоящее из элементов между o1 и o2.

TreeSet<String> states = new TreeSet<String>();
states.add("Германия");
states.add("Франция");
states.add("Италия");
states.add("Великобритания");

System.out.println(states.first()); // получим первый - самый меньший элемент
System.out.println(states.last()); // получим последний - самый больший элемент

// получим поднабор от одного элемента до другого
SortedSet<String> set = states.subSet("Германия", "Франция");
System.out.println(set);
// элемент из набора, который больше текущего
String greater = states.higher("Германия");
// элемент из набора, который больше текущего
String lower = states.lower("Германия");
// возвращаем набор в обратном порядке
NavigableSet<String> navSet = states.descendingSet();
// возвращаем набор в котором все элементы меньше текущего
SortedSet<String> setLower=states.headSet("Германия");
// возвращаем набор в котором все элементы больше текущего
SortedSet<String> setGreater=states.tailSet("Германия");

На консоль будет выведено:

Великобритания
Франция
[Германия, Италия]

Arrays

В классе Arrays собрано множество методов для работы с массивами.

Их можно разделить на четыре группы:

• заполнение;
• сортировка;
• поиск;
• сравнение.

Отметим, что все эти методы являются статическими, а, значит, должны быть вызваны по имени класса Arrays. Массив, к которому применяют эти методы, является одним из параметров указанных методов и должен быть описан как type_ [], где type_ может быть одним из примитивных типов byte, short, int, long, char, float, double.

Заполнение массива

Первая группа методов - `fill()`` - заполняет указанным значением value:

а) массив целиком static void fill(type_[] a, type_ value) Это метод удобно использовать, когда необходимо задать значение по умолчанию для всех элементов массива:

int[] a = new int[10];
Arrays. fill(a, 0); // обнуление всех элементов массива

б) часть массива от индекса from включительно до индекса to исключительно static void fill(type_[] a, int from, int to, type_ value),

Arrays. fill(a, 0, a. length / 2, 1);

Сортировка массива

Вторая группа методов sort() сортирует:

а) массив в порядке возрастания числовых значений или объекты в их естественном порядке:

'''java Arrays.sort(b); '''

б) в порядке возрастания часть массива от индекса from включительно до индекса to исключительно:

Arrays. sort(b, a. length / 2, a. length);

в) массив или его часть с элементами класса Object по правилу, заданному объектом с, реализующим интерфейс Comparator: static void sort(Object[] a, Comparator c)

Интерфейс Comparator позволяет определить собственные методы сравнения: compare(Object obj1, Object obj2) и проверки на эквивалентность - equals(Object obj).

int compare(Object obj1, object obj2) - возвращает:

• отрицательное число, если obj1 в каком-то смысле меньше obj2;
• 0, если они считаются равными;
• положительное число, если obj1 больше obj2.

boolean equals (Object obj) - сравнивает данный объект с объектом `obj, возвращая true, если объекты совпадают в каком-либо смысле, заданном этим методом.

или static void sort(Object[] a, int from, int to, Comparator c). Стоит заметить, что параметром метода сортировки с использованием компаратора не может быть базовый тип, в этом случае надо передавать соответствующий класс-оболочку. Для примера рассмотрим задачу сортировки массива по младшей цифре.

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void printArrI(Integer[] a) {
        for (int x : a) {
            System.out.print(" " + x);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxRange = 100;
        System.out.println("Сортировка массива через компаратор");
        Integer[] aInt = new Integer[10];
        for (int i = 0; i < aInt.length; ++i) {
            aInt[i] = (int) (Math.random() * (maxRange + 1));
        }
        printArrI(aInt);
        class Comp implements Comparator<Integer> {
            @Override
            public int compare(Integer obj1, Integer obj2) {
                int m1 = obj1 % 10;
                int m2 = obj2 % 10;
                if (m1 < m2)
                    return -1;
                else if (m1 > m2)
                    return 1;
                else
                    return 0;
            }
        }
        Comp c = new Comp();
        Arrays.sort(aInt, c);
        printArrI(aInt);
    }
}

На экране появится (для массива случайных чисел):

Сортировка массива через компаратор
45 45 26 7 61 98 19 98 22 84
61 22 84 45 45 26 7 98 98 19

Изменяя условия в компараторе, мы можем менять порядок сортировки массива (например,поменяв, местами
 команды return -1 и return 1, мы изменим сортировку по возрастанию на сортировку по убыванию
 значений младшей цифры элементов массива).

### Поиск в массиве

Третья группа методов - `binarySearch()` - организует бинарный поиск, при котором метод возвращает
индекс найденного элемента массива. Подробно бинарный поиск рассматривается ниже.

Если элемент не найден, то возвращается отрицательное число, означающее индекс, с которым элемент
 был бы вставлен в массив в заданном порядке, с обратным знаком.

Класс Arrays поддерживает поиск элемента element в упорядоченном по возрастанию массиве:

`static int binarySearch(type_[] a, type_ element)`

```java
int[] a = { 3, 5, 8, 9, 11};
int k = Arrays. binarySearch(a, 8);
System. out.println(" " + k);

В этом примере программа вернет число 2.

Сравнение массивов

Четвертая группа методов - equals () - сравнивает массивы: static boolean equals (type[] al, type[] a2)

Массивы считаются равными, если они имеют одинаковую длину и равные элементы массивов с одинаковыми индексами. В этом случае метод возвращает true.

public class Program {
    public static void printArr(int[] a) {
        for (int x : a) {
            System.out.print(" " + x);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxRange = 100;
        int[] a = new int[10];
        for (int i = 0; i < a.length; ++i) {
            a[i] = (int) (Math.random() * (maxRange + 1));
        }
        printArr(a);
        int[] b = a.clone();
        if (Arrays.equals(a, b))
            System.out.println("Массивы равны");
        else
            System.out.println("Массивы не равны");
        System.out.println("Массив b после сортировки: ");
        Arrays.sort(b);
        printArr(b);
        if (Arrays.equals(a, b))
            System.out.println("Массивы равны");
        else
            System.out.println("Массивы не равны");
        int k = Arrays.binarySearch(b, a[0]);
        System.out.println("Элемент " + a[0] + " b имеет индекс " + k);
        System.out.println("\nЗаполнение части массива b: ");
        Arrays.fill(b, 0, b.length / 2, 0);
        printArr(b);
//поиск в массиве произвольного числа 35
        k = Arrays.binarySearch(b, 35);
        System. out.println("Элемент " + 35 + " имеет индекс " + k);
    }
}