Java Лекция 5

Коллекции Java

Денис Син
План лекции

Иерархия коллекций

List, ArrayList, LinkedList

Deque, PriorityQueue

Map, Set, HashMap, TreeMap

Сортировка и компараторы

Основные операции

Сравнение коллекций

2
Иерархия коллекций

3
Коллекции List<String> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
Основные интерфейсы: Map<String, Integer> map = new HashMap<>();
• Collection: корневой интерфейс для списков,
множеств, очередей.
• Map: хранит пары «ключ-значение» (не наследует
Collection).

4
Наследники Collection List<String> names = new ArrayList<>();
[Link]("Анна");
Основные наследники: [Link]("Иван");
• List (LinkedList, ArrayList) [Link]([Link](0)); // Анна
• Set (HashSet, LinkedHashSet, TreeSet)
• Queue (LinkedList, PriorityQueue)

5
Интерфейс Map Map<String, Integer> ages = new HashMap<>();
[Link]("Анна", 25);
Основные наследники: [Link]("Иван", 30);
• HashMap [Link]([Link]("Иван")); // 30
• LinkedHashMap
• TreeMap

6
List vs Set vs Map

7
Итерация по коллекциям. Foreach vs Iterator

List<String> fruits = [Link]("Яблоко", "Апельсин");

for (String fruit : fruits) {
[Link](fruit);
}

Set<Integer> set = new HashSet<>([Link](10, 20, 30));

Iterator<Integer> iterator = [Link]();
while ([Link]()) {
[Link]([Link]());
}

8
Выбор коллекции // Телефонная книга
Map<String, String> phoneBook = new HashMap<>();
Используйте [Link]("Анна", "+7-999-123-45-67");
• ArrayList, если нужен быстрый доступ по индексу. [Link]("Иван", "+7-987-654-32-10");
• HashSet — для проверки уникальности элементов.
• HashMap — для быстрого поиска по ключу.
• LinkedList — если частые вставки/удаления в
середине

9
Интерфейс List List<String> list = new ArrayList<>();
[Link]("A"); // Индекс 0
Основные характеристики: [Link]("B"); // Индекс 1
• Упорядоченная коллекция с доступом по индексу. [Link]([Link](0)); // A
• Допускает дубликаты и null-значения.
• Базовые методы: add(), get(), remove(), size().

10
ArrayList ArrayList<Integer> numbers = new ArrayList<>();
[Link](10);
Особенности: [Link](20);
• Реализация на основе массива. [Link](1, 15); // Вставка по индексу 1
• Быстрый доступ по индексу (O(1)). [Link](numbers); // [10, 15, 20]
• Медленные вставка/удаление в середине (O(n)).

11
LinkedList LinkedList<String> names = new LinkedList<>();
[Link]("Анна");
Особенности: [Link]("Иван"); // В начало
• Реализация на основе двусвязного списка. [Link]("Мария"); // В конец
• Быстрые вставка/удаление в начале и конце [Link](1); // Удаление элемента "Анна"
(O(1)). [Link](names); // [Иван, Мария]
• Медленный доступ по индексу (O(n)).

12
ArrayList vs LinkedList

13
ArrayList vs LinkedList

14
Пример. Реализовать историю посещений сайта

LinkedList<String> history = new LinkedList<>();

[Link]("Page1");
[Link]("Page2");
// Удаляем старые элементы, если размер > 10
if ([Link]() > 10) {
[Link]();
}

15
Интерфейс Map Map<String, Integer> ages = new HashMap<>();
[Link]("Анна", 25);
Основные наследники: [Link]("Иван", 30);
• HashMap [Link]([Link]("Иван")); // 30
• LinkedHashMap
• TreeMap

16
Структура Map

17
HashMap
• Хранит элементы в виде массива бакетов.
• Каждый бакет представляет собой цепочку
(связанный список или дерево, начиная с Java 8)
для разрешения коллизий.
• Производительность зависит от равномерного
распределения хэш-кодов.
• При переполнении бакетов происходит
перераспределение (rehash).

18
TreeMap Map<String, Integer> treeMap = new TreeMap<>();
[Link]("apple", 10);
Структура: [Link]("banana", 20);
•Реализован на основе красно-чёрного дерева.
•Гарантирует логарифмическое время работы для
операций добавления, удаления и поиска.
Особенности:
•Ключи должны быть сравнимыми.
•Элементы автоматически сортируются.

19
TreeMap
Структура:
•Реализован на основе красно-чёрного дерева.
•Гарантирует логарифмическое время работы для
операций добавления, удаления и поиска.
Особенности:
•Ключи должны быть сравнимыми.
•Элементы автоматически сортируются.

20
LinkedHashMap Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
[Link]("apple", 10);
[Link]("banana", 20);
Особенности:
• Сохраняет порядок вставки или порядок доступа.
• Подходит для реализации LRU-кэшей.
Внутренняя структура:
• Помимо хэш-таблицы, использует двусвязный
список для поддержки порядка.

21
LinkedHashMap
Особенности:
• Сохраняет порядок вставки или порядок доступа.
• Подходит для реализации LRU-кэшей.
Внутренняя структура:
• Помимо хэш-таблицы, использует двусвязный
список для поддержки порядка.

22
Операции с Map Map<String, String> map = new HashMap<>();
[Link]("key1", "value1");
[Link]("key2", "value2");
• Добавление элементов: put(key, value)
• Получение значения: get(key)
// Получение значения
• Удаление элемента: remove(key) String val = [Link]("key1");

// Удаление элемента
[Link]("key2");

23
Полезные методы if ([Link]("key1")) {
[Link]("Ключ существует!");
}
• containsKey(Object key): Проверяет наличие
ключа.
• containsValue(Object value): Проверяет наличие
значения.
• size(): Возвращает количество пар.
• isEmpty(): Проверяет, пуста ли карта.

24
 Полезные методы [Link]("key3", "value3");

[Link]("key1", (k, v) -> v == null ? "newValue" : v +

• putIfAbsent(K key, V value): Добавляет элемент,
"_updated");
если ключ отсутствует.
• compute(K key, BiFunction [Link]("key1", "mergeValue", (oldVal, newVal) ->
remappingFunction): Пересчитывает значение по oldVal + "_" + newVal);
ключу.
• merge(K key, V value, BiFunction
remappingFunction): Объединяет значение, если
ключ уже присутствует.

25
LinkedHashMap HashMap Оптимизации
Поддержка порядка через дополнительные • Использование методов hashCode() и equals(). • Выбор правильной реализации в
ссылки в узлах. • Порог загрузки (load factor) и зависимости от задачи.
перераспределение элементов. • Настройка начальной емкости и
коэффициента загрузки.

TreeMap
• Балансировка красно-чёрного дерева.
• Работа с компараторами.

26
 Sets (Множества) private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing
Map
• Коллекции, в которых объект может
private static final Object PRESENT = new Object();
присутствовать только один раз.
• Реализованы на базе соответствующих Maps: public boolean add(E e) {
HashSet, LinkedHashSet, TreeSet. return [Link](e, PRESENT)==null;
}

27
Очереди
• Queue – интерфейс, описывающий структуру данных "очередь", работающую по принципу FIFO (первый пришёл –
первый вышел).
• Применяется для моделирования очередей, планирования задач и т.п.
• Deque (Double Ended Queue) – расширение интерфейса Queue, позволяющее выполнять операции добавления и
удаления элементов с обоих концов очереди.
• Поддерживает как FIFO, так и LIFO-поведение (например, для реализации стека).

28
Реалиазации Queue // Пример использования PriorityQueue
Queue<Integer> priorityQueue = new PriorityQueue<>();
[Link](5);
LinkedList:Реализует интерфейсы Queue и Deque.
[Link](2);
• Позволяет использовать один объект для
[Link](8);
реализации обеих структур. [Link]("Первый элемент очереди: " +
PriorityQueue: [Link]());
• Очередь с приоритетами, элементы сортируются
согласно естественному порядку или
компаратору.
• Не допускает null элементов.
ArrayDeque:Реализует интерфейс Deque.
• Высокая производительность при использовании
как стека или очереди.

29
Comparable и Runnable public interface Comparable<T> {
public int compareTo(T o);
• Есть много интерфейсов из стандартной
}
библиотеки
• Runnable – для реализации одно метода запуска public interface Runnable {
какой-то логики /**
• Comparable – для сравнивания объектов * Runs this operation.
*/
void run();
}

30
Операции с Queue Queue<String> queue = new LinkedList<>();
[Link]("Первый");
[Link]("Второй");
Добавление элементов:
• offer(e) – добавляет элемент в очередь
[Link]([Link]()); // "Первый"
(возвращает false, если элемент не может быть
[Link]([Link]()); // "Первый", удалён из
добавлен).
очереди
• add(e) – добавляет элемент, но выбрасывает
исключение при невозможности добавления.
Извлечение элементов:
• poll() – возвращает и удаляет первый элемент или null,
если очередь пуста.
• remove() – возвращает и удаляет первый элемент,
выбрасывая исключение, если очередь пуста.
Просмотр элемента:
• peek() – возвращает первый элемент без удаления
или null, если очередь пуста.
• element() – возвращает первый элемент без удаления,
выбрасывая исключение при пустой очереди.

31
Работа с Deque Deque<Integer> deque = new ArrayDeque<>();
[Link](10); // Добавляем в начало
[Link](20); // Добавляем в конец
Двусторонний доступ:
• Методы для работы с обоими концами
[Link]([Link]()); // 10
очереди: addFirst(), addLast(), offerFirst(), offerLast().
[Link]([Link]()); // 20
• Методы
удаления: pollFirst(), pollLast(), removeFirst(), removeLast(
// Использование Deque как стека
).
[Link](5); // Аналог addFirst
Использование в качестве стека:
[Link]([Link]()); // 5
• push(e) – добавляет элемент в начало
(аналогично addFirst(e)).
• pop() – удаляет и возвращает первый элемент
(аналогично removeFirst()).

32
Comparable

public interface Comparable<T>{

/**
* @param o the object to be compared.
* @return a negative integer, zero, or a positive integer as this object
* is less than, equal to, or greater than the specified object.
*/
int compareTo(T o);
}

/*Применяется в случае, если сравниваемые объекты

не реализуют Comparable*/
public interface Comparator<T> {
int compare(T o1, T o2);
}

33
Iterable: интерфейс, умеющий участвовать в for loop

Iterable<T> collection = ...

Iterator<T> i = [Link]();
while ([Link]()) {
T e = [Link]();
if (e...)
[Link]();
}

Iterable<T> collection = ...

for (T e: collection) {
...
}

34
Сравнение коллекций

35
Всем больше Java