12. Расскажите про реализации интерфейса Set

В множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов.

Все классы, реализующие интерфейс Set, внутренне поддерживаются реализациями Map.

В HashSet порядок элементов определяется по сложному алгоритму.

TreeSet - объекты хранятся отсортированными по возрастанию в порядке сравнения

LinkedHashSet - хранение элементов в порядке добавления.

Множества часто используются для проверки принадлежности, чтобы вы могли легко проверить, принадлежит ли объект заданному множеству, поэтому на практике обычно выбирается реализация HashSet, оптимизированная для быстрого поиска.

HashSet

Класс HashSet реализует интерфейс Set, основан на хэш-таблице, а также поддерживается с помощью экземпляра HashMap. В HashSet элементы не упорядочены, нет никаких гарантий, что элементы будут в том же порядке спустя какое-то время.

HashSet хранит элементы с помощью HashMap. Хоть и для добавления элемента в HashMap он должен быть представлен в виде пары «ключ-значение», в HashSet добавляется только значение.

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

Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел. Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен (override). HashSet хранит элементы таким образом, чтобы элемент можно было очень быстро найти.

Методы contains и indexOf у ArrayList проходят последовательно по элементам списка в поисках нужного элемента, а метод contains у HashSet ищет элемент многократно быстрее, так как использует совсем другой подход: элементы находятся в так называемых «корзинах» (на иллюстрации — 16 серых корзин), которые выбираются исходя из значений самих элементов (на иллюстрации — 7 зелёных элементов множества).

Конструкторы HashSet :

• Создание пустого набора с начальной емкостью (16) и со значением коэффициента загрузки (0.75) по умолчанию public HashSet();
• Создание множества из элементов коллекции public HashSet(Collection c);
• Создание множества с указанной начальной емкостью и со значением коэффициента загрузки по умолчанию (0.75) public HashSet(int initialCapacity);
• Создание множества с указанными начальной емкостью и по умолчанию 16, коэффициентом загрузки по умолчанию 0.75 public HashSet(int initialCapacity, float loadFactor);

Методы аналогичны методам ArrayList за исключением того, что метод add(Object o) добавляет объект в множество только в том случае, если его там нет. Возвращаемое методом значение — true, если объект добавлен, и false, если нет.

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

Реализация HashSet не синхронизируется. Если многократные потоки получают доступ к набору хеша одновременно, а один или несколько потоков должны изменять набор, то он должен быть синхронизирован внешне. Это лучше всего выполнить во время создания, чтобы предотвратить случайный несинхронизируемый доступ к набору:

Set<E> set = Collections.synchronizedSet(new HashSet<E>());

LinkedHashSet

Класс LinkedHashSet расширяет класс HashSet, не добавляя никаких новых методов. Класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор.

Также, как и HashSet, LinkedHashSet не синхронизируется. Поэтому при использовании данной реализации в приложении с множеством потоков, часть из которых может вносить изменения в набор, следует на этапе создания выполнить синхронизацию.

TreeSet

Проще говоря, TreeSet это отсортированная коллекция, которая расширяет класс AbstractSet и реализует интерфейс NavigableSet.

Особенности:

• Хранит уникальные элементы
• Не сохраняет порядок вставки элементов
• Сортирует элементы в порядке возрастания
• не потокобезопасный

TreeSet не поддерживает добавление null, однако если бы вы написали свой собственный компаратор, который поддерживает null, то не было бы никаких проблем использовать null в качестве ключа

В этой реализации объекты сортируются и хранятся в порядке возрастания в соответствии с их естественным порядком. TreeSet использует самобалансирующееся двоичное дерево поиска.

По сравнению с HashSet производительность TreeSet находится на нижней стороне. Такие операции, как add , remove и search , занимают O (log n) время, в то время как такие операции, как печать n элементов в отсортированном порядке, требуют O (n) время.

Будучи самобалансирующимся двоичным деревом поиска, каждый узел двоичного дерева содержит дополнительный бит, который используется для определения цвета узла, которыйявляется красным или черным. Во время последующих вставок и удалений эти «цветные» биты

помогают обеспечить более или менее сбалансированное дерево.

SortedSet

По умолчанию сортировка производится привычным способом, но можно изменить это поведение через интерфейс Comparable.

Предыдущий вопрос: 11. Расскажите про интерфейс Set.

Следующий вопрос: 13. В чем отличия TreeSet и HashSet?

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку:напишите мне