Статьи
Утилиты Telegram YouTube Отзывы

Коллекции: list, set, map

Видеогайд

7 мая 2018

Тэги: Collections, Java.

Содержание

  1. Список (list)
  2. Набор (set)
  3. Словарь (map)

Под коллекциями в программировании подразумевают объекты, которые хранят внутри себя какой-либо набор значений и предоставляют набор методов для обращения к этим значениям. В Java можно выделить 3 наиболее часто используемых типа коллекций: списки (list), наборы (set) и словари (map). При объявлении коллекции типизируются каким-либо типом, т.е. одна коллекция хранит данные одного типа.

Список (list)

Списки в Java реализуют интерфейс List, который, в свою очередь, расширяет интерфейс Collection. Список позволяет хранить любые значения, в том числе повторяющиеся. Итерация (обход) списка происходит в порядке добавления элементов. Т.е. элемент, добавленный первым, при итерации также будет первым.

List<String> list = new ArrayList<>();
list.add("яблоко");
list.add("ананас");
list.add("яблоко");
System.out.println(list); // На экране увидим: [яблоко, ананас, яблоко]

Две наиболее частые реализации интерфейса List – это ArrayList и LinkedList.

Класс ArrayList построен на базе массива. Это означает, что доступ по индексу (порядковому номеру элемента) происходит очень быстро. А добавление элементов в середину списка в общем случае довольно затратно, т.к. нужно будет подвинуть вправо каждый элемент, который идёт после добавляемого. С удалением такая же штука. Кроме того, массив, лежащий в основе этой структуры данных, имеет конечное количество свободных ячеек и если их перестанет хватать, придётся создать новый массив большего размера, перенеся в него все элементы из исходного. Но всё это скрыто внутри реализации ArrayList.

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

Казалось бы, у каждой реализации списка свои плюсы и минусы, однако в последних версиях Java ArrayList был достаточно хорошо оптимизирован и на практике можно всё время выбирать его без ущерба для производительности в любых задачах.

Набор (set)

Интерфейс Set представляет собой набор уникальных значений и тоже наследуется от Collection. У этого интерфейса есть несколько реализаций, но каждая из них гарантирует, что каждое значение в наборе уникально.

Сравнение любых двух объектов между собой в Java происходит при помощи методов equals() и hashCode() из базового класса Object. Метод equals выполняет полное сравнение элементов, тогда как hashCode только лишь вычисляет хеш-функцию, которая может принимать одинаковые значения для разных элементов. Соотношение между этими двумя методами всегда такое: если для двух объектов hashCode возвращает одинаковое значение, то equals при этом может быть false, однако если equals возвращает true, то hashCode обязан возвращать одинаковые значения. При создании собственных классов, если их предполагается использовать в наборах или словарях, вы должны переопределить эти два метода, чтобы коллекции работали с ними корректно.

Теперь рассмотрим три основные реализации интерфейса Set.

Первая из них – это HashSet. Когда мы будет выполнять проход по этому набору, то порядок элементов на первый взгляд нам покажется хаотичным. Однако на самом деле он будет зависеть от значения хэш-функции для каждого элемента. Также обратите внимание, что мы два раза добавляем «яблоко» в набор, однако в результате увидим его только один раз.

Set<String> hashSet = new HashSet<>();
hashSet.add("яблоко");
hashSet.add("яблоко"); // дубль
hashSet.add("ананас");
hashSet.add("банан");
System.out.println(hashSet); // На экране увидим: [банан, яблоко, ананас]

Следующая реализация – это LinkedHashSet, которая расширяет предыдущую. Основное различие заключается в том, что при обходе элементов мы будем видеть их в порядке добавления:

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("яблоко");
linkedHashSet.add("яблоко");
linkedHashSet.add("ананас");
linkedHashSet.add("банан");
System.out.println(linkedHashSet); // [яблоко, ананас, банан]

Ну а третья реализация под названием TreeSet имеет в своей основе структуру данных «красно-чёрное дерево», что позволяет сортировать элементы автоматически:

Set<String> treeSet = new TreeSet<>();
treeSet.add("яблоко");
treeSet.add("яблоко");
treeSet.add("ананас");
treeSet.add("банан");
System.out.println(treeSet); // [ананас, банан, яблоко]

Поэтому если хотите сохранять порядок добавления элементов – используйте LinkedHashSet, а если хотите получить отсортированный набор – тогда используйте TreeSet.

Словарь (map)

Также смотрите статью Удобные методы работы с Map.

Интерфейс Map представляет собой набор из пар элементов типа «ключ-значение». На русский язык это переводят по-разному: карта, маппинг, хэш-таблица. Но мне больше всего нравится аналогия со словарём, так как с этим набором мы примерно так и работаем: имеем какое-то слово (ключ) и пытаемся найти его перевод (значение).

Словарь гарантирует, что каждому ключу соответствует одно и только одно значение. Если по уже существующему ключу положить новое значение, то оно перезатрёт старое. При работе с ключами также используются методы equals и hashCode. И по аналогии с Set здесь мы также имеем три основных реализации интерфейса Map.

Первая реализация – это HashMap, которая не гарантирует никакого порядка элементов при обходе. Обратите внимание, что при повторном добавлении элемента с тем же ключом, мы теряем первое значение:

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("яблоко", 1);
hashMap.put("яблоко", 2); // повторное добавление
hashMap.put("ананас", 3);
hashMap.put("банан", 4);
System.out.println(hashMap); // На экране увидим: {банан=4, яблоко=2, ананас=3}

Ещё одна реализация – это LinkedHashMap, которая сохраняет порядок добавления:

Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("яблоко", 1);
linkedHashMap.put("яблоко", 2);
linkedHashMap.put("ананас", 3);
linkedHashMap.put("банан", 4);
System.out.println(linkedHashMap); // {яблоко=2, ананас=3, банан=4}

Ну и третья популярная реализация интерфейса Map – это TreeMap, которая сортирует ключи по порядку:

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("яблоко", 1);
treeMap.put("яблоко", 2);
treeMap.put("ананас", 3);
treeMap.put("банан", 4);
System.out.println(treeMap); // {ананас=3, банан=4, яблоко=2}

Поэтому если хотите сохранять порядок добавления элементов – используйте LinkedHashMap, а если хотите получить отсортированный по ключам набор – тогда используйте TreeMap.



Комментарии

02.07.2022 03:45 Игорь

Шикарно объяснено.

29.09.2022 22:22 Андрей

Согласен с предыдущим комментарием

02.10.2022 21:42 Ангелина

спасибо за содержательное объяснение

06.03.2023 16:37 Айрат

У автора талант! понятно объясняет.

09.04.2023 22:35 Termitter

"перезатрёт старое" Избыточность: или "затрет старое" или "перезапишет".
Другое уточнение: "в которой каждый элемент имеет ссылку на предыдущий элемент и на следующий." Это уже двунаправленный linkedlist. "Также имеется ссылка на начало и на конец списка". А это уже queue (ссылка на начало) и deque (ссылка на начало и конец).
Но объяснение отличное. Спасибо!

Добавить комментарий

×

devmark.ru