Как работает коллекция 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() для проверки на дубликаты.

Пример:

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        Set<String> uniqueNames = new HashSet<>();

        uniqueNames.add("Alice");
        uniqueNames.add("Bob");
        uniqueNames.add("Alice"); // Этот элемент не будет добавлен, т.к. уже есть

        System.out.println("Размер Set: " + uniqueNames.size()); // Выведет 2

        for (String name : uniqueNames) {
            System.out.println(name); // Порядок вывода может быть произвольным
        }

        System.out.println("Содержит Bob? " + uniqueNames.contains("Bob")); // Выведет true

        uniqueNames.remove("Alice");
        System.out.println("Размер после удаления: " + uniqueNames.size()); // Выведет 1
    }
}