Как работает коллекция Set в Java?

Set в Java — это коллекция, которая не содержит повторяющихся элементов. Она основана на хеш-таблицах или сбалансированных деревьях и обеспечивает:

• Уникальность элементов: Гарантируется, что каждый элемент в Set присутствует только один раз.
• Отсутствие порядка: Чаще всего элементы в Set не хранятся в определенном порядке (за исключением специфических реализаций, таких как LinkedHashSet).
• Быстрый поиск, вставка и удаление: Операции add(), remove(), contains() обычно имеют среднюю временную сложность O(1) для HashSet, при условии хорошего хеширования.

Основные методы:

• add(E element): Добавляет указанный элемент в Set. Если элемент уже присутствует, возвращает false, иначе true.
• remove(Object o): Удаляет указанный элемент из Set, если он присутствует.
• contains(Object o): Проверяет наличие указанного элемента в Set.
• size(): Возвоащает количество элементов в Set.
• isEmpty(): Проверяет, пуст ли Set.

Наиболее распространенные реализации:

• HashSet: Основан на хеш-таблице. Предлагает высокую производительность для основных операций, но не гарантирует порядок элементов.
• LinkedHashSet: Основан на хеш-таблице и связанном списке. Сохраняет порядок добавления элементов.
• TreeSet: Основан на сбалансированном дереве (Red-Black Tree). Элементы хранятся в отсортированном порядке. Требует, чтобы элементы реализовывали интерфейс Comparable или предоставляли Comparator.

Работа HashSet основана на методах hashCode() и equals() объектов, которые добавляются в коллекцию. При добавлении элемента вычисляется его хеш-код. Используя этот хеш-код, определяется "корзина" в хеш-таблице, куда потенциально может быть помещен элемент. Затем, в этой корзине (которая может быть представлена связанным списком или деревом в Java 8+), используется метод equals() для проверки на дубликаты.

Пример:

java