1. Список коллекций
Как ты можешь помнить, в Java есть удобный инструмент для хранения объектов одинаковых типов – коллекции.
Попробуем вспомнить основные интерфейсы коллекций:
List, Set, Map и Queue.
Как водится, нет правильных или неправильных инструментов, если использовать их по назначению. А для этого мы с тобой должны хорошенько разобраться в их особенностях, чтобы знать, когда и какую коллекцию использовать.
1. List
Давай начнем с самой часто используемой коллекции.
List максимально схож с самым обычным массивом. Название же нам говорит о том, что это список (list).
Эта коллекция дает нам возможность удобно хранить в себе список объектов одного типа, не заботясь о размере самой коллекции, как мы это делали, используя массивы. Обращение к элементам коллекции происходит по индексу. Если мы точно знаем, на каком месте находится объект и нам необходимо часто к нему обращаться, при этом нам не нужно часто добавлять или удалять элементы, List — это идеальный вариант.
2. Set
Set (множество) имеет совсем другую структуру.
В первую очередь, Set стоит использовать, когда нам нужно хранить уникальные объекты. Допустим, это набор авторов в библиотеке, где каждый автор уникален. Но мы не можем просто так обратиться к нашему набору авторов и достать из него конкретного автора. Функционал Set-а дает нам возможность быстро проверить, представлен ли конкретный автор в нашей библиотеке, например проверить его наличие в коллекции Set. Также есть возможность пройтись по всей коллекции, по каждому элементу, но это не оптимально.
То есть, в нашей библиотеке Set может служить чем-то вроде набора всех авторов, для быстрой проверки, представлен ли этот автор в библиотеке.
3. Map
Map (словарь) больше похожа на картотеку, где каждая ячейка подписана, и в ней мы можем хранить как отдельные объекты, так и целые структуры. Map стоит использовать в случаях, когда необходимо сохранить соответствие одного значения к другому.
В Map это называется соответствие ключ – значение.
С такой структурой в нашей библиотеке мы сможем использовать объект автора как ключ, а список (List) книг как значение. Таким образом, проверив в Set наличие автора в библиотеке, мы сможем по этому же объекту автора достать List с его книгами из Map.
4. Queue
Queue (очередь) – представляет собой коллекцию, которая построена как очередь. Причем эта очередь может быть не только LIFO (Last In First Out – последний зашел, первый вышел), но и FIFO (First In First Out – первый зашей, первый вышел). А еще очередь может быть двунаправленная, с выходами с обоих сторон.
Этот инструмент удобен в случаях, когда объекты, поступающие в наш класс, метод, необходимо использовать в порядке их поступления. Например, в нашей библиотеке.
Мы можем добавлять вновь прибывших посетителей в Queue и по очереди их обслуживать, выдавая книги, за которыми они к нам приходят.
Как мы с тобой можем видеть, все структуры хороши, если использовать их по назначению. И в пределах одного примера, библиотеки, мы использовали все четыре типа коллекций.
2. Сложность
Как уже было отмечено, коллекции, которые мы рассматривали выше, это интерфейсы, а значит у них должны быть реализации, которые мы и будем использовать.
Поскольку забивать гвозди микроскопом — не самая лучшая идея, нам стоит знать, какую именно реализацию коллекции лучше использовать в той или иной ситуации.
Чаще всего, выбирая тот или иной инструмент, мы смотрим на 2 показателя:
- насколько этот инструмент подходит под задачу
- насколько быстро будет происходить работа с ним
Если с выбором подходящего под задачу инструмента мы кое-как разобрались, то скорость его работы – это что-то новенькое.
Показатель скорости работы часто выражают через временную сложность и обозначают большой буквой О.
Что вообще такое эта временная сложность?
Простыми словами, эта сложность указывает на время отработки алгоритма, который заложен в коллекцию для того или иного действия (добавление, удаление элемента, поиск).
ArrayList vs LinkedList
Давай рассмотрим это на примере двух реализаций интерфейса List — ArrayList и LinkedList.
Частично про различие этих двух реализаций упоминается в этой статье.
Внешне, работа с этими коллекциями похожа:
List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
List<String> linkedList = new LinkedList<>();
linkedList.add(String);
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
Как ты мог заметить, в обоих случаях мы одинаково добавляем, берем и удаляем элемент из списка. Это из-за того, что мы создаем реализации на основе одно интерфейса. Но на этом сходство у них заканчивается.
Благодаря разной реализации интерфейса List эти две структуры имеют разную эффективность при разном использовании.
Рассмотрим пример операции удаления и добавления элемента.
Если нам нужно будет удалить элемент из середины списка ArrayList, каждый раз мы будем переписывать остальную часть списка, следующую за элементом, который мы удаляем.
Допустим, у нас есть список из 5-ти элементов и нам нужно удалить 3-й.
List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
list.remove(2);
В таком случае после удаления у нас освободится одна ячейка, и мы будем вынуждены перезаписать 4-й элемент на место 3-го, а 5-й на место 4-го.
Это максимально неэффективно.
То же самое будет происходить и при добавлении элемента в середину списка.
LinkedList же устроен по-другому. Добавление или удаление элементов из него происходит быстро, так как нам всего лишь нужно изменить ссылки в предыдущем и следующем элементе, исключив из цепочки элементов объект, который мы удаляем.
На примере того же списка из 5-ти элементов, удалив из него 3-й, мы должны просто поменять ссылку на следующий элемент во 2-м и ссылку на предыдущий в 4-м элементе.
То же самое, только наоборот, происходит при добавлении элемента в список.
Обратите внимание, насколько меньше действий нам необходимо произвести в LinkedList в сравнении с ArrayList. А это всего лишь 5 элементов. Будь в списке 100 и больше элементов, превосходство LinkedList было бы более ощутимо.
Но как поменяется ситуация, если мы будем обращаться к элементу по индексу?
Тут все будет ровно наоборот.
Так как ArrayList устроен как обычный массив, нам будет очень просто взять любой элемент по его индексу. Мы просто переместим указатель на определенное место и возьмем из ячейки элемент.
Но в LinkedList так просто не получится. Нам придется пройтись по всем элементам массива, чтобы найти элементы с определенным индексом. Только в данном случае имеет смысл называть это не индекс, а порядковый номер.
Давай попробуем выразить это все через большую О?
Начнем с обращения к элементу по индексу.
В ArrayList это происходит в одно действие, вне зависимости от местоположения элемента в списке. В начале он или в конце.
Временная сложность в данном случае будет О(1).
В LinkedList нам придется перебрать то количество элементов, индекс которого нам нужен.
Временная сложность для такого действия будет О(n) – где n – это индекс элемента, который нам нужен.
Получается, под скобки большого О мы помещаем число, которое соответствует количеству производимых действий.
Вернемся к удалению и добавлению?
Начнем с LinkedList.
Так как нам не нужно делать большое количество действий для добавления или удаления элемента, и скорость этой операции никак не зависит от того, где находится элемент, сложно будет выглядеть так – О(1) и называется константной.
Сложность этой же операции для ArrayList будет уже О(n) и называется линейной.
В алгоритмах с линейной сложностью время работы напрямую зависит от количества элементов, которые предстоит обработать. Также это может зависеть и от положения элемента, в начале списка или ближе к концу.
Сложность еще бывает логарифмической. Выглядит она вот так — O(log n).
В качестве примера можем рассмотреть отсортированный TreeSet список из 10-ти чисел, в котором нам нужно найти число 2.
Так как список отсортирован и в нем нет дубликатов, мы можем разделить его пополам и проверить, в какой части списка осталось искомое число, откинуть одну из частей и повторить действия снова, пока не дойдем до искомого элемента. В итоге мы найдем число, обработав log(n) количество элементов.
Давай взглянем на таблицу, в которой описаны сложности остальных коллекций.
| По индексу | По ключу | Поиск | Вставка в конец | Вставка в середину | Удаление | |
|---|---|---|---|---|---|---|
| ArrayList | O(1) | N/A | О(n) | O(1) | O(n) | O(n) |
| LinkedList | O(n) | N/A | O(n) | O(1) | O(1) | O(1) |
| HashSet | N/A | O(1) | O(1) | N/A | O(1) | O(1) |
| TreeSet | N/A | O(1) | O(log n) | N/A | O(log n) | O(log n) |
| HashMap | N/A | O(1) | O(1) | N/A | O(1) | O(1) |
| TreeMap | N/A | O(1) | O(log n) | N/A | O(log n) | O(log n) |
| ArrayDeque | N/A | N/A | O(n) | O(1) | O(1) | O(1) |
Теперь, когда у нас с тобой есть таблица, в которой указана временная сложность для популярных коллекций, мы можем ответить на вопрос, почему из такого количества коллекций мы чаще всего используем ArrayList, HashSet и HashMap.
Они просто максимально эффективны для большинства задач :)
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ