Collections Framework #

А зачем коллекции, если есть массивы? #

Массив - это контейнер, который хранит фиксированное количество элементов одного типа.

int[] numbers = new int[5]; // массив на 5 чисел
numbers[0] = 10;
numbers[1] = 20;
// ...

В чём проблема?

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

int[] students = new int[100];

Добавили сюда 100 студентов. А теперь добавим ещё одного. Как? Да никак. Мы не можем просто написать что-то вроде students.add(...). Размер массива уже определен. Придётся:

1. Создать новый массив большего размера
2. Перенести в новый массив элементы старого массива
3. Только теперь добавить ещё одного студента

Удобно? Ну, не сказал бы.

Что такое Collections Framework? #

Collections Framework (или «коллекции») - это готовый набор классов и интерфейсов в Java, который предоставляет удобные структуры данных для хранения и обработки групп объектов. Про классы и интерфейсы мы пока не знаем, но оно на данный момент нам и не нужно. Сейчас нас интересуют прежде всего готовые штуки, которыми мы можем пользоваться вместо неудобных массивов. Как устроены интерфейсы и почему одни классы реализуют другие интерфейсы - это тема ООП, к ней мы вернёмся позже.

Простыми словами, коллекции - это «умные контейнеры», которые умеют:

• автоматически увеличиваться при добавлении новых элементов;
• удалять элементы без лишних сложностей;
• искать, сортировать, перебирать элементы разными способами.

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

Основные "виды" коллекций #

В Java коллекции делятся на несколько больших групп по своему поведению. Мы рассмотрим три самые популярные:

Какой из типов коллекции использовать, очевидно, зависит от задачи:

• Нужен просто удобный массив? - ArrayList
• Нужен набор исключительно уникальных значений? - HashSet
• Нужны пары ключ-значение? - HashMap

На самом деле коллекций намного больше, чем я дам в этой лекции. Дело в том, что бОльшая часть коллекций на данном этапе нам не понадобятся, т.к. они решают крайне специфичные задачи. Если интересно, то ниже будут показаны все виды коллекций, а также их иерархия, исключительно для общего развития.

Iterable
   │
Collection - базовый "родитель" для большинства коллекций
   ├── List - список, уопрядоченная последовательность. Доступ по индексу, дубликаты
   │    ├── ArrayList - динамический массив. Быстрый доступ по индексу
   │    ├── LinkedList - двусвязный список. Эффективная работа с концами
   │    ├── Vector - динамический массив, устарел
   │    ├── Stack - стек LIFO, устарел
   │    └── CopyOnWriteArrayList - массив + копирование при изменении
   │
   ├── Set - множество. Дубликаты не допускаются
   │    ├── HashSet - хеш-таблица. Быстрый поиск
   │    ├── LinkedHashSet хеш-таблица + связный список. Порядок вставки
   │    ├── TreeSet - красно-чёрное дерево. Сортировка
   │    ├── EnumSet - специальная битовая структура
   │    └── CopyOnWriteArraySet
   │
   └── Queue - очередь. Обработка элементов в опр. порядке
        ├── PriorityQueue - бинарная куча. Первым извлекается элемент с высш. приоритетом
        └── Deque - двусторонняя очередь. Возможность работы с обоих концов
             ├── ArrayDeque - циклическая очередь
             └── LinkedList

Map - отображение ключ -> значение
 ├── HashMap - хеш-таблица. Быстрый поиск по ключу
 ├── LinkedHashMap - хеш-таблица + связный список. Порядок вставки
 ├── TreeMap - красно-чёрное дерево. Ключи отсортированы
 ├── Hashtable - хеш-таблица. Устаревшая реализация Map
 ├── WeakHashMap - хеш-таблица. Ключи могут быть съедены сборщиком мусора
 ├── IdentityHashMap - хеш-таблица. Сравнение ключей через ==, а не equals()
 ├── EnumMap - массивоподобная структура
 └── ConcurrentHashMap - хеш-таблица с безопасным конкурентным доступом

ArrayList - самая используемая коллекция #

ArrayList - это как массив, но который может расти. Он реализует интерфейс List.

import java.util.ArrayList;
// ...
ArrayList<String> friends = new ArrayList<>();

Мы создали пустой список, в который можно класть строки.

Основные методы:

• add(элемент) - добавить в конец списка.
• add(индекс, элемент) - вставить на указанную позицию.
• get(индекс) - получить элемент по индексу.
• remove(индекс) - удалить элемент по индексу.
• remove(объект) - удалить конкретный объект (первое вхождение).
• size() - вернуть количество элементов.
• contains(объект) - проверить, есть ли элемент в списке.
• clear() - удалить все элементы.
• set(индекс, элемент) - заменить существующий элемент.
• isEmpty() - проверить, пустой ли список. Заменяет if (list.size() == 0)

Пример:

import java.util.ArrayList;

public class ArrayListDemo {
    public static void main(String[] args) {
        // Создаём список друзей
        ArrayList<String> friends = new ArrayList<>();
        
        // Добавляем
        friends.add("Анна");
        friends.add("Борис");
        friends.add("Виктор");
        
        System.out.println("Размер списка: " + friends.size()); // 3
        
        // Выводим всех
        for (int i = 0; i < friends.size(); i++) {
            System.out.println(friends.get(i));
        }
        
        // Добавляем в середину
        friends.add(1, "Галина"); // теперь на позиции 1 будет Галина, Борис сдвинется
        
        // Удаляем
        friends.remove("Борис"); // удаляем по значению
        
        // Проверяем наличие
        if (friends.contains("Анна")) {
            System.out.println("Анна есть в списке!");
        }
        
        // Перебор в стиле for-each
        for (String name : friends) {
            System.out.println(name);
        }
        
        friends.set(1, "Галина"); 
        if (friends.isEmpty()) { 
	        System.out.println("Список пуст"); 
		}
    }
}

Важно: ArrayList хранит элементы в порядке добавления, и к ним можно обращаться по индексу - как к массиву, но размер не фиксирован.

Важно2: ArrayList можно выводить с помощью println() без лишних циклов или Arrays.toString():

ArrayList<Integer> ints = new ArrayList<>();
ints.add(1);
ints.add(2);
ints.add(3);

IO.println(ints); // Вывод будет нормальным

"Под капотом" список - это всё ещё обычный массив. Просто список делает бОльшую часть работы за вас. Он внутри создаёт массив и засовывает туда элементы. Место в массиве закончилось? Список сам создаст новый массив большего размера, переместит туда старые элементы и засунет новые. Вам об этом париться не надо.

Отступление по поводу remove() #

Метод remove() - перегруженный. О перегрузке говорилось в четвёртой лекции. То есть, метод имеет две версии:

Первая - удаляет элемент по индексу:

ArrayList<Integer> numbers = new ArrayList<>();

numbers.add(10);
numbers.add(20);
numbers.add(30);

numbers.remove(1); // удаляем число 20 (оно имеет индекс 1)

Вторая - удаляет элемент по значению. Но тут нюанс: если список хранит тип данных Integer, то при вызове, например, remove(1) единица в качестве аргумента ВСЕГДА означает индекс. Если же нужно из такого списка удалить элемент по значению, то передать нужно не int, а именно Integer:

ArrayList<Integer> numbers = new ArrayList<>();

numbers.add(10);
numbers.add(20);
numbers.add(30);

numbers.remove(Integer.valueOf(10)); // удаляем число 10 

Сравнение ArrayList и массива #

Set (множество) #

Set гарантирует, что в нём не будет дубликатов. Это полезно, например, для хранения уникальных имён или идентификаторов.

Основные классы: HashSet (не запоминает порядок) и TreeSet (хранит элементы в отсортированном порядке).

Основные методы:

• add(элемент) - добавить элемент во множество
• remove(элемент) - удалить элемент по значению (во множестве нет индексов, а соответственно и удалить элемент по индексу, очевидно, нельзя)
• contains(элемент) - проверка наличия элемента во множестве
• size() - сколько элементов хранится во множестве
• isEmpty() - проверить, пустое ли множество
• clear() - удалить все элементы

HashSet #

Пример с HashSet:

import java.util.HashSet;

public class HashSetDemo {
    public static void main(String[] args) {
        HashSet<String> uniqueNames = new HashSet<>();
        
        uniqueNames.add("Анна");
        uniqueNames.add("Борис");
        uniqueNames.add("Анна"); // не добавится, т.к. уже есть
        
        System.out.println(uniqueNames.size()); // 2
        
        // Перебор (порядок не гарантируется!)
        for (String name : uniqueNames) {
            System.out.println(name);
        }
        
        // Проверка
        if (uniqueNames.contains("Борис")) {
            System.out.println("Борис есть");
        }
        
        uniqueNames.remove("Анна"); // удаляем Анну из множества
        uniqueNames.clear(); // очищаем множество
        IO.println(uniqueNames.isEmpty()); // true, множество пустое
    }
}

Множество не запрещает нам несколько раз добавить один и тот же элемент. Просто в случае дублирования он молча не добавит этот элемент. Без ошибок и предупреждений.

TreeSet #

Если нужна сортировка, то используем TreeSet:

TreeSet<Integer> numbers = new TreeSet<>();

numbers.add(50);
numbers.add(10);
numbers.add(30);
numbers.add(20);

System.out.println(numbers); // [10, 20, 30, 50]

Пока что больше о TreeSet вам знать не нужно.

Map - ключ-значение #

Map не является наследником Collection, но тоже входит в Collections Framework. Она хранит пары: ключ → значение. Ключи уникальны.

Основные методы:

• put(ключ, значение) - добавить (или перезаписать в случае дублирования ключа) пару ключ-значение
• get(ключ) - получить значение по ключу
• remove(ключ) - удалить пару по ключу
• containsKey(ключ) - проверить существование ключа
• containsValue(значение) - проверить существование значения
• size() - количество пар в map
• isEmpty() - аналогично прошлым коллекциям
• clear() - аналогично
• keySet() - возвращает множество, содержащее все ключи map

Пример: телефонная книга — имя (ключ) → номер телефона (значение).

import java.util.HashMap;

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> phoneBook = new HashMap<>();
        
        // Добавляем пары
        phoneBook.put("Анна", 123456);
        phoneBook.put("Борис", 789012);
        phoneBook.put("Анна", 999999); // заменит предыдущее значение для ключа "Анна"
        
        // Получаем значение по ключу
        int annaPhone = phoneBook.get("Анна");
        System.out.println("Телефон Анны: " + annaPhone); // 999999
        
        // Проверяем наличие ключа
        if (phoneBook.containsKey("Борис")) {
            System.out.println("Номер Бориса: " + phoneBook.get("Борис"));
        }
        
        // Перебор всех ключей
        for (String name : phoneBook.keySet()) {
            System.out.println(name + " -> " + phoneBook.get(name));
        }
    }
}

Обращаю внимание на кусок из примера:

phoneBook.put("Анна", 123456);
phoneBook.put("Анна", 999999);

Ключи в map уникальны. Если ключ уже существует, то put() заменит старое значение.

Замечание о примитивах #

Коллекции могут хранить только объекты, а не примитивные типы (int, double, boolean и т.д.). Для этого в Java есть классы-обёртки: Integer, Double, Boolean и др. Автоматическая упаковка (autoboxing) позволяет писать list.add(5) вместо list.add(Integer.valueOf(5)) - компилятор сделает это за вас. Поэтому вы можете спокойно добавлять числа в ArrayList<Integer>.

Обо всех всяких словах типа "autoboxing", "классы-обёртки" и прочее (вы не поверите) мы поговорим позже.

Практическая работа №5 #

1. Работа со списком оценок (ArrayList) #

Условие:
Создайте ArrayList<Integer> для хранения оценок студентов (например, от 1 до 5).
Заполните его 10 случайными оценками (или введите вручную).
Реализуйте следующие действия (каждое в отдельном цикле или отдельном блоке):

• Выведите все оценки через пробел.
• Найдите и выведите среднее арифметическое всех оценок.
• Удалите все оценки ниже 3 (двойки и единицы) — используйте цикл с проверкой условия. Учтите, после удаления элемента, остальные элементы "сдвигаются" и их индексы меняются. Для корректной работы цикла начинать его нужно с конца списка.
• Добавьте в конец списка оценку 5.
• Выведите итоговый список.

Пример вывода (для наглядности):

Исходные оценки: 4 2 5 3 1 4 5 2 3 4  
Среднее: 3.3  
После удаления низких оценок: 4 5 3 4 5 3 4  
После добавления 5: 4 5 3 4 5 3 4 5

2. Уникальные слова в тексте (HashSet) #

Условие:
Дан текст (строка), состоящий из нескольких предложений. Разбейте его на слова (используйте split(" ") или split("\\s+")).
Создайте HashSet<String>, чтобы хранить только уникальные слова (регистр игнорируйте - можно перевести всё в нижний регистр).
Выведите количество уникальных слов и сами слова (в любом порядке).
Дополнительно: проверьте, содержится ли в тексте слово «java» (или любое другое) и выведите результат.

Пример:
Вход: "Java is great. Java is fun. I hate Java."
Уникальные слова: [java, is, great, fun, i, hate] (порядок может быть другим)
Количество: 6
Содержит "java"? Да.

3. Частота слов (HashMap) #

Условие:
Возьмите тот же текст (или любой другой).
С помощью HashMap<String, Integer> подсчитайте, сколько раз каждое слово встречается в тексте (регистр игнорировать).
Выведите все слова и их частоту.
Затем найдите слово с максимальной частотой и выведите его и количество.

Пример:
Вход: "apple banana apple orange banana apple"
Вывод:
apple=3
banana=2
orange=1
Самое частое слово: apple (3 раза)

4. Объединение двух списков без дубликатов (ArrayList + HashSet) #

Условие:
Даны два ArrayList<Integer> с числами (могут содержать повторения).
Создайте новый ArrayList<Integer>, который будет содержать все элементы из первого и второго списков, но без дубликатов (каждое число встречается только один раз).
Порядок элементов не важен.
Подсказка: используйте HashSet для удаления дубликатов, а затем преобразуйте его обратно в ArrayList.

Пример:
Список А: [1, 2, 3, 4]
Список Б: [3, 4, 5, 6]
Результат: [1, 2, 3, 4, 5, 6] (или в другом порядке)

5*. Телефонный справочник с несколькими номерами (HashMap<String, ArrayList<String>>) #

Дополнительное задание.
Условие:
Создайте программу, которая эмулирует телефонный справочник.
Используйте HashMap<String, ArrayList<String>>, где ключ - имя человека (строка), а значение - список его телефонных номеров (строки).

Реализуйте в main простое текстовое меню (без бесконечного цикла, можно сделать один раз набор операций):

1. Добавить контакт - если имя уже существует, добавить новый номер в его список; если нет - создать запись с одним номером.
2. Удалить номер у контакта - по имени и номеру (если номер найден, удалить его; если после удаления список номеров пуст, удалить и сам контакт).
3. Найти все номера по имени - вывести список номеров или сообщение, что контакта нет.
4. Вывести весь справочник - на экран все имена и их номера.

Все действия выполните последовательно (можно захардкодить тестовые вызовы, без ввода с клавиатуры, чтобы проверить работу методов).
Например:

// Добавляем
addContact("Анна", "123-45-67");
addContact("Анна", "765-43-21");
addContact("Борис", "111-22-33");
// Выводим весь справочник
// Удаляем номер у Анны
removeNumber("Анна", "123-45-67");
// Ищем Анну
findContact("Анна");
// Снова выводим справочник