Тема 19. Множества - BelyiZ/JavaCourses GitHub Wiki
Содержание:
Интерфейс Set
Set — это интерфейс в Java коллекции (Java Collection Framework) и является подинтерфейсом Collection, поэтому он обладает всеми функциями Collection.
Set - это неупорядоченная Collection (unordered Collection), не допускающая дублирования элементов и содержащая максимум 1 null-элемент.
Если вы намеренно добавите дублированный элемент в Set, это действие будет проигнорировано и Set не изменится.
Является программной моделью математического понятия "множество".
Set создана для хранения множества элементов.
Иерархия Set включает в себя два интерфейса — SortedSet и NavigableSet — и три основных класса.
HashSet — коллекция, которая не позволяет хранение одинаковых элементов благодаря содержанию в себе
объекта HashMap. Он использует для хранения данных хэш-таблицы. В качестве ключа используется добавляемый элемент, а в
качестве значения — объект-пустышка (new Object()). Из-за особенностей реализации порядок элементов не гарантируется
при добавлении.
HashSet поддерживается HashMap. Он не дает никаких гарантий относительно последовательности элементов при их итерации.
LinkedHashSet — подобная HashSet, в которой элементы объединены между собой в порядковый список. В этом случае
элементы хранятся в том же порядке, в котором и добавляются. То есть благодаря тому, что в основе лежит LinkedHashMap
вместо HashMap порядок элементов при обходе коллекции является идентичным порядку добавления элементов.
TreeSet — коллекция, которая использует для хранения элементов упорядоченное по значениям дерево. Аналогично другим
классам-реализациям интерфейса Set содержит в себе объект NavigableMap, что и обуславливает его поведение То есть
содержит в себе TreeMap коллекцию, которая использует для хранения своих элементов сбалансированное красно-черное
бинарное дерево. Благодаря этому операции add, remove и contains в этой коллекции займут гарантированное время,
равное log(n). А это — весомое преимущество по сравнению с другими имплементациями интерфейса Set.
Отличия HashSet, LinkedHashSet и TreeSet
HashSetхранит элементы в произвольном порядке, но зато быстро ищет. Подходит, если порядок не важен, но важна скорость. Более того, для оптимизации поиска,HashSetбудет хранить элементы так, как ему удобно.LinkedHashSetбудет хранить элементы в порядке добавления, но зато работает медленнее.TreeSetхранит элементы отсортированными.
Особенности
Операции над множеством
С множеством можно делать только три операции:
- добавлять элементы во множество,
- удалять элементы из множества и проверять,
- есть ли во множестве определенный элемент.
Отсутствие порядка
У элементов этой коллекции нет номеров.
Нельзя получить элемент по его индексу или записать значение в коллекцию по определенному индексу.
Методов get() и set() у множества нет.
Уникальность элементов
Все элементы множества уникальны. В отличие от списка, в множестве один элемент может быть только раз. Объект или находится во множестве, или нет: третьего не дано. Напрмер нельзя во "множество цветов" трижды добавить "черный цвет". Он там либо есть, либо его нет.
Поиск элементов
Когда вы добавляете во множество новый элемент, удаляете элемент, или проверяете наличие элемента, внутри метода выполняется поиск элемента.
Элементы коллекции и переданный элемент сравниваются сначала по hashCode(), а если hashCode() совпадают, по equals.
Сравнение со списком
Интерфейсы Set и Java List очень похожи друг на друга и представляет собой набор элементов.
Тем не менее, есть некоторые существенные различия. Эти различия отражены в методах, которые содержат интерфейсы Set и List.
- один и тот же элемент не может встречаться в наборе более одного раза. Это отличается от списка, где каждый элемент может встречаться более одного раза.
- элементы в Set не имеют гарантированного внутреннего порядка. Элементы в списке имеют внутренний порядок, и элементы могут быть повторены в этом порядке.
Коллекция List (Список) похожа на команду футболистов.
Можно добавить футболиста и присвоить ему номер из конца списка.
Можно вставить и в середину, если очень нужно (но часть номеров футблистов нужно передвинуть).
У каждого футболиста есть номер. Можно выбрать футболиста по номеру или заменить. Можно удалить из команды футболиста с конкретным номером. Ну и наконец, можно узнать количество всех фуиболистов в команде.
Коллекция Set (Множество) больше похожа на футболистов, которые находятся в толпе без номеров.
В толпу можно добавить футболиста, можно удалить футболиста из толпы. Но фиксированного номера у него нет.
Вот для таких случаев понадобится множество Set и его самый популярный представитель — класс HashSet.
Операции с Set
1. add() - добавляет элемент в множество
Этот метод унаследован от интерфейса Collection.
Set setA = new HashSet();
setA.add("element 1");
setA.add("element 2");
setA.add("element 3");
Также возможно преобразовать Set в List, создав List и вызвав его метод addAll(), передав Set в качестве параметра.
Set set = new HashSet();
set.add("123");
set.add("456");
List list = new ArrayList();
list.addAll(set);
После запуска этого примера список будет содержать строковые элементы 123 и 456 – так как это были все элементы, присутствующие в наборе при вызове List.addAll(set).
2. remove() - удаляет элемент из множества
set.remove("object-to-remove");
Невозможно удалить объект на основе индекса в наборе, поскольку порядок элементов зависит от его реализации.
Интерфейс Java Set имеет метод с именем removeAll(), который удаляет все элементы в наборе, также присутствующие в другой коллекции.
В теории множеств это называется разницей между множеством и другой коллекцией.
Set set = new HashSet();
set.add("one");
set.add("two");
set.add("three");
Set set2 = new HashSet();
set2.add("three");
set.removeAll(set2);
После запуска набор будет содержать элементы String один и два.
Третий элемент был удален, потому что он присутствовал в set2, который был задан как параметр для set.removeAll(set2).
3. contains() - определяет, есть ли элемент в множестве
Возможно проверить, содержит ли Set данный элемент (объект), вызвав метод contains():
Set set = new HashSet();
set.add("123");
set.add("456");
boolean contains123 = set.contains("123");
После выполнения этого кода переменная contains123 будет содержать значение true, потому что Set на самом деле содержит строку 123.
Чтобы определить, содержит ли набор элемент, он будет внутренне выполнять итерации своих элементов и сравнивать каждый с объектом, переданным в качестве параметра. Для сравнения используется метод равенства.
Поскольку можно добавить нулевые значения, также можно проверить, содержит ли набор нулевое значение:
set.add(null);
containsElement = set.contains(null);
System.out.println(containsElement);
Очевидно, что если входной параметр для contains() имеет значение null, метод contains() не будет использовать метод equals() для сравнения с каждым элементом, а вместо этого использует оператор ==.
Интерфейс Set также имеет метод, который сохраняет все элементы в наборе, также присутствующие в другой коллекции. Все найденные в наборе элементы, которых нет в другой коллекции, будут удалены.
В теории множеств это называется пересечением между множеством и другой коллекцией.
Set set = new HashSet();
set.add("one");
set.add("two");
set.add("three");
Set set2 = new HashSet();
set2.add("three");
set2.add("four");
set.retainAll(set2);
После запуска набор будет содержать только элемент String три, так как присутствует как в set, так и в set2.
4. size() - возвращает размер множества Размер набора – это количество элементов, содержащихся в наборе.
Set set = new HashSet();
set.add("123");
set.add("456");
set.add("789");
int size = set.size();
После выполнения переменная размера будет иметь значение 3, потому что созданный в примере набор имеет 3 добавленных элемента.
5. clear() - удаляет все элементы из коллекции
set.clear();
6. isEmpty() - возвращает true если множество пустое, и false если там есть хотя бы 1 элемент
Set set = new HashSet();
boolean isEmpty = set.isEmpty();
После запуска этого кода переменная isEmpty будет содержать значение true, потому что Set пуст (в нем нет элементов).
Возможно проверить, является ли Set пустым, сравнив значение, возвращаемое методом size() с 0:
Set set = new HashSet();
boolean isEmpty =(set.size() == 0);
После выполнения этого кода переменная isEmpty будет содержать значение true, потому что метод Set size() возвращает 0 – в примере не содержится элементов.
Когда удобно применять:
- Добавить элемент в набор.
- Перебор элементов набора.
- Удалить элементы набора.
- Удалить все элементы набора.
- Добавить все элементы из другой коллекции.
- Удалить все элементы из другой коллекции.
- Сохранить все элементы, присутствующие в другой коллекции.
- Установить размер набора.
- Проверить, содержится ли элемент.
- Конвертировать в список.