По какому принципу работает Set

Принципы работы Set в Java

Set - это коллекция, которая содержит только уникальные элементы (без дубликатов). Это один из самых часто используемых интерфейсов в Java Collections Framework.

Основной принцип: уникальность

SET гарантирует, что в нём не будет двух одинаковых элементов. Проверка осуществляется через методы equals() и hashCode().

Set<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("apple"); // Второе добавление "apple" игнорируется

System.out.println(fruits.size()); // Выведет 2
for (String fruit : fruits) {
    System.out.println(fruit); // apple, banana
}

Типы Set и их характеристики

1. HashSet — хеш-таблица

Set<Integer> numbers = new HashSet<>();
numbers.add(10);
numbers.add(5);
numbers.add(20);
numbers.add(5); // Игнорируется

// Неупорядоченный результат
for (Integer num : numbers) {
    System.out.println(num); // 5, 10, 20 (порядок не гарантирован)
}

Характеристики:

• Порядок элементов не гарантирован
• Быстрые операции: O(1) для add/remove/contains
• Основан на HashMap
• Позволяет null элементы (один null)
• Не синхронизирован

2. LinkedHashSet — хеш-таблица + двусвязный список

Set<Integer> numbers = new LinkedHashSet<>();
numbers.add(10);
numbers.add(5);
numbers.add(20);

// Сохраняет порядок добавления
for (Integer num : numbers) {
    System.out.println(num); // 10, 5, 20 (в порядке добавления)
}

Характеристики:

• Сохраняет порядок вставки элементов
• O(1) для операций (как HashSet)
• Немного медленнее HashSet (из-за поддержки двусвязного списка)
• Позволяет null

3. TreeSet — красно-чёрное дерево

Set<Integer> numbers = new TreeSet<>();
numbers.add(10);
numbers.add(5);
numbers.add(20);
numbers.add(5); // Игнорируется

// Отсортированный порядок
for (Integer num : numbers) {
    System.out.println(num); // 5, 10, 20 (в отсортированном порядке)
}

Характеристики:

• Элементы хранятся в отсортированном порядке
• O(log n) для операций
• Требует Comparable или Comparator
• Не позволяет null элементы
• NavigableSet методы (headSet, tailSet, floor, ceiling)

Как работает уникальность: equals() и hashCode()

public class User {
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        User user = (User) obj;
        return age == user.age && Objects.equals(name, user.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

Set<User> users = new HashSet<>();
users.add(new User("John", 30));
users.add(new User("Jane", 25));
users.add(new User("John", 30)); // Не добавится (equals == true)

System.out.println(users.size()); // 2

Как HashSet проверяет уникальность

1. Вычисляет hashCode() нового элемента
2. Найдёт bucket с этим hash значением
3. Если bucket пуст — добавит элемент
4. Если bucket содержит элементы — проверит equals() с каждым
5. Если equals() вернул false для всех — добавит элемент
6. Если equals() вернул true хотя бы для одного — игнорирует

// Пример неправильного hashCode/equals
public class BadUser {
    private String name;
    
    @Override
    public int hashCode() {
        return 0; // Все элементы получат одинаковый hash!
    }
    
    @Override
    public boolean equals(Object obj) {
        return true; // Все объекты считаются равными!
    }
}

Set<BadUser> badUsers = new HashSet<>();
badUsers.add(new BadUser("John"));
badUsers.add(new BadUser("Jane")); // Не добавится!
badUsers.add(new BadUser("Bob"));  // Не добавится!

System.out.println(badUsers.size()); // 1 (неправильно!)

Операции Set

Set<String> set1 = new HashSet<>(Arrays.asList("a", "b", "c"));
Set<String> set2 = new HashSet<>(Arrays.asList("b", "c", "d"));

// Объединение (Union)
Set<String> union = new HashSet<>(set1);
union.addAll(set2); // {a, b, c, d}

// Пересечение (Intersection)
Set<String> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // {b, c}

// Разность (Difference)
Set<String> difference = new HashSet<>(set1);
difference.removeAll(set2); // {a}

Лучшие практики

// 1. Выбирай правильный Set для задачи
Set<Integer> hashSet = new HashSet<>();     // Быстро, неупорядочено
Set<Integer> linkedSet = new LinkedHashSet<>(); // Сохраняет порядок
Set<Integer> treeSet = new TreeSet<>();     // Отсортировано

// 2. Переопредели equals и hashCode для кастомных объектов
public class Product {
    private Long id;
    @Override
    public boolean equals(Object o) { ... }
    @Override
    public int hashCode() { ... }
}

// 3. Помни про null
Set<String> set = new HashSet<>();
set.add(null);  // OK для HashSet/LinkedHashSet
set.add(null);  // Дубликат, не добавится

// TreeSet не допускает null
Set<String> treeSet = new TreeSet<>();
treeSet.add(null); // NullPointerException!

// 4. Используй потокобезопасные версии при необходимости
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();

Сравнение производительности

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