📋 План лекции

🧮 Что такое множество?

Множество (set) — это математическая концепция, описывающая_collection (коллекцию, набор) уникальных объектов. Уникальных — значит, что каждый элемент встречается в множестве только один раз.

В математике множества обозначаются фигурными скобками: {1, 2, 3, 4, 5}. Важно понимать:

• 🔹 Порядок элементов не важен: {1, 2, 3} — это то же самое, что {3, 1, 2}.
• 🔹 Дубликаты невозможны: {1, 2, 2, 3} — это некорректная запись множества. Правильно: {1, 2, 3}.
• 🔹 Элементы могут быть любого типа: числа, строки, объекты — что угодно.

💻 Зачем множества нужны в программировании?

В программировании множества используются для решения множества практических задач:

• 🚫 Удаление дубликатов: если у вас есть список с повторяющимися элементами, множество автоматически уберёт повторы.
• 🔍 Быстрая проверка наличия элемента: «Есть ли этот пользователь в списке заблокированных?» — множество ответит за доли миллисекунды.
• 🔗 Поиск пересечений: «Какие друзья есть у обоих пользователей?» — пересечение двух множеств.
• 🎯 Объединение данных: «Собери всех уникальных посетителей с трёх сайтов в один список».
• 🧹 Фильтрация: «Оставь только те элементы, которых нет в чёрном списке» — разность множеств.

🔌 Интерфейс Set в Java

В Java множества представлены интерфейсом Set, который находится в пакете java.util. Интерфейс Set наследуется от интерфейса Collection (коллекция), но добавляет главное ограничение: все элементы должны быть уникальными.

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

// Создаём пустое множество строк
Set<String> fruits = new HashSet<>();

// Добавляем элементы
fruits.add("Яблоко");
fruits.add("Банан");
fruits.add("Апельсин");
fruits.add("Яблоко"); // Дубликат! Не добавится

System.out.println(fruits); // [Банан, Апельсин, Яблоко]
System.out.println(fruits.size()); // 3 (не 4!)

⚡ HashSet: быстрое множество

HashSet — это самая распространённая реализация интерфейса Set. Внутри она использует структуру данных, которая называется хеш-таблица (hash table).

Как работает хеш-таблица? Когда вы добавляете элемент, Java вычисляет его хеш-код (hash code) — специальное число, которое служит «адресом» элемента в памяти. Благодаря этому поиск, добавление и удаление происходят очень быстро — практически мгновенно.

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

Set<Integer> numbers = new HashSet<>();

numbers.add(5);
numbers.add(10);
numbers.add(15);
numbers.add(5); // Дубликат, не добавится

System.out.println(numbers); // [5, 10, 15] (порядок не гарантирован!)
System.out.println(numbers.contains(10)); // true
System.out.println(numbers.contains(20)); // false

🔗 LinkedHashSet: сохраняем порядок

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

Под капотом LinkedHashSet использует и хеш-таблицу (для быстрого поиска), и связный список (для сохранения порядка). Это немного медленнее, чем обычный HashSet, но зато предсказуемо.

import java.util.LinkedHashSet;
import java.util.Set;

Set<String> days = new LinkedHashSet<>();

days.add("Понедельник");
days.add("Вторник");
days.add("Среда");
days.add("Четверг");
days.add("Пятница");

System.out.println(days); 
// [Понедельник, Вторник, Среда, Четверг, Пятница]
// Порядок сохранён!

🌳 TreeSet: отсортированное множество

TreeSet — это реализация Set, которая автоматически сортирует элементы в естественном порядке (для чисел — по возрастанию, для строк — по алфавиту).

Под капотом TreeSet использует структуру данных красно-чёрное дерево (red-black tree) — это сбалансированное двоичное дерево поиска. Благодаря этому операции выполняются за время O(log n) — чуть медленнее, чем HashSet, но всё равно очень быстро.

import java.util.Set;
import java.util.TreeSet;

Set<Integer> numbers = new TreeSet<>();

numbers.add(50);
numbers.add(10);
numbers.add(30);
numbers.add(20);
numbers.add(40);

System.out.println(numbers); // [10, 20, 30, 40, 50]
// Элементы отсортированы!

// Дополнительные методы TreeSet:
System.out.println(((TreeSet<Integer>)numbers).first()); // 10
System.out.println(((TreeSet<Integer>)numbers).last());  // 50

⚖️ Сравнение трёх реализаций Set

🛠️ Основные операции с множеством

Интерфейс Set предоставляет несколько базовых методов для работы с элементами:

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

Set<String> fruits = new HashSet<>();

// ➕ Добавление элемента
fruits.add("Яблоко");      // true (добавлено)
fruits.add("Банан");       // true
fruits.add("Яблоко");      // false (уже есть)

// ❌ Удаление элемента
fruits.remove("Банан");    // true (удалено)
fruits.remove("Груша");    // false (не было)

// 🔍 Проверка наличия
System.out.println(fruits.contains("Яблоко")); // true
System.out.println(fruits.contains("Банан"));  // false

// 📏 Размер множества
System.out.println(fruits.size()); // 1

// 🗑️ Очистка множества
fruits.clear();
System.out.println(fruits.isEmpty()); // true

🔄 Перебор элементов множества

Множество можно перебирать тремя способами, как и любую другую коллекцию в Java:

Способ 1: Цикл for-each (самый простой)

Set<String> fruits = Set.of("Яблоко", "Банан", "Апельсин");

for (String fruit : fruits) {
    System.out.println(fruit);
}

Способ 2: Итератор

Iterator<String> iterator = fruits.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

Способ 3: Stream API (современный способ)

fruits.forEach(fruit -> System.out.println(fruit));

// Или ещё короче:
fruits.forEach(System.out::println);

🔀 Операция: Объединение (Union)

Объединение двух множеств — это новое множество, содержащее все элементы из обоих множеств (без дубликатов).

В математике обозначается: A ∪ B

В Java для объединения используется метод addAll():

Set<Integer> setA = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> setB = new HashSet<>(Set.of(3, 4, 5, 6));

// Создаём новое множество для результата
Set<Integer> union = new HashSet<>(setA);
union.addAll(setB);

System.out.println(union); // [1, 2, 3, 4, 5, 6]
// Элементы 3 и 4 встречаются только один раз!

🎯 Операция: Пересечение (Intersection)

Пересечение двух множеств — это новое множество, содержащее только те элементы, которые есть в обоих множествах одновременно.

В математике обозначается: A ∩ B

В Java для пересечения используется метод retainAll():

Set<Integer> setA = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> setB = new HashSet<>(Set.of(3, 4, 5, 6));

// Создаём копию setA и оставляем только общие элементы
Set<Integer> intersection = new HashSet<>(setA);
intersection.retainAll(setB);

System.out.println(intersection); // [3, 4]
// Только те элементы, которые есть и в A, и в B

🧹 Операция: Разность (Difference)

Разность двух множеств A и B — это новое множество, содержащее те элементы из A, которых нет в B.

В математике обозначается: A \ B (A минус B)

В Java для разности используется метод removeAll():

Set<Integer> setA = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> setB = new HashSet<>(Set.of(3, 4, 5, 6));

// Создаём копию setA и удаляем из неё элементы setB
Set<Integer> difference = new HashSet<>(setA);
difference.removeAll(setB);

System.out.println(difference); // [1, 2]
// Только те элементы из A, которых нет в B

🔄 Симметрическая разность

Симметрическая разность — это элементы, которые принадлежат либо A, либо B, но не обоим сразу. То есть «уникальные» элементы обоих множеств.

В математике обозначается: A △ B

В Java напрямую такой операции нет, но её можно получить комбинацией:

Set<Integer> setA = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> setB = new HashSet<>(Set.of(3, 4, 5, 6));

// Способ 1: (A ∪ B) \ (A ∩ B)
Set<Integer> union = new HashSet<>(setA);
union.addAll(setB);

Set<Integer> intersection = new HashSet<>(setA);
intersection.retainAll(setB);

union.removeAll(intersection);
System.out.println(union); // [1, 2, 5, 6]

// Способ 2: (A \ B) ∪ (B \ A)
Set<Integer> diff1 = new HashSet<>(setA);
diff1.removeAll(setB);

Set<Integer> diff2 = new HashSet<>(setB);
diff2.removeAll(setA);

diff1.addAll(diff2);
System.out.println(diff1); // [1, 2, 5, 6]

🧹 Практика: удаление дубликатов из списка

Одна из самых частых задач — убрать повторяющиеся элементы из списка. Множество делает это элегантно:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RemoveDuplicates {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Анна");
        names.add("Борис");
        names.add("Анна");  // дубликат
        names.add("Виктор");
        names.add("Борис"); // дубликат
        names.add("Галина");
        
        System.out.println("Было: " + names);
        // [Анна, Борис, Анна, Виктор, Борис, Галина]
        
        // Превращаем список в множество (дубликаты исчезают)
        Set<String> uniqueNames = new HashSet<>(names);
        
        // Если нужен снова список — превращаем обратно
        List<String> uniqueList = new ArrayList<>(uniqueNames);
        
        System.out.println("Стало: " + uniqueList);
        // [Анна, Борис, Виктор, Галина] (порядок может отличаться)
    }
}

👥 Практика: поиск общих друзей

Классическая задача социальных сетей — найти общих друзей двух пользователей. Множества решают её в одну операцию:

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

public class CommonFriends {
    public static void main(String[] args) {
        // Друзья пользователя "Маша"
        Set<String> mashaFriends = new HashSet<>();
        mashaFriends.add("Аня");
        mashaFriends.add("Боря");
        mashaFriends.add("Вика");
        mashaFriends.add("Дима");
        
        // Друзья пользователя "Петя"
        Set<String> petyaFriends = new HashSet<>();
        petyaFriends.add("Боря");
        petyaFriends.add("Вика");
        petyaFriends.add("Гриша");
        petyaFriends.add("Дима");
        petyaFriends.add("Егор");
        
        // Находим общих друзей (пересечение)
        Set<String> commonFriends = new HashSet<>(mashaFriends);
        commonFriends.retainAll(petyaFriends);
        
        System.out.println("Общие друзья: " + commonFriends);
        // [Боря, Вика, Дима]
        
        System.out.println("Их количество: " + commonFriends.size());
        // 3
    }
}

📝 Практика: уникальные слова в тексте

Задача: подсчитать количество уникальных слов в тексте. Множество — идеальное решение:

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

public class UniqueWords {
    public static void main(String[] args) {
        String text = "Мама мыла раму мама мыла окно рама чистая окно чистое";
        
        // Разбиваем текст на слова (по пробелам)
        String[] words = text.split(" ");
        
        // Помещаем все слова в множество (приводим к нижнему регистру)
        Set<String> uniqueWords = new HashSet<>();
        for (String word : words) {
            uniqueWords.add(word.toLowerCase());
        }
        
        System.out.println("Всего слов: " + words.length);           // 10
        System.out.println("Уникальных слов: " + uniqueWords.size()); // 6
        System.out.println("Слова: " + uniqueWords);
        // [мама, мыла, раму, окно, рама, чистая, чистое]
    }
}

📦 Проверка: является ли A подмножеством B?

Часто нужно проверить, все ли элементы множества A содержатся в множестве B. Для этого используется метод containsAll():

Set<Integer> setA = new HashSet<>(Set.of(1, 2));
Set<Integer> setB = new HashSet<>(Set.of(1, 2, 3, 4, 5));

// Является ли A подмножеством B?
boolean isSubset = setB.containsAll(setA);
System.out.println(isSubset); // true

// А наоборот?
boolean isSuperset = setA.containsAll(setB);
System.out.println(isSuperset); // false

🔒 Неизменяемые множества (Immutable Set)

Иногда нужно создать множество, которое нельзя изменять после создания. Это полезно для констант и защиты данных от случайных изменений.

Начиная с Java 9, для этого есть удобный метод Set.of():

// Создаём неизменяемое множество
Set<String> colors = Set.of("Красный", "Зелёный", "Синий");

// colors.add("Жёлтый"); // ❌ UnsupportedOperationException!
// colors.remove("Красный"); // ❌ UnsupportedOperationException!

System.out.println(colors); // [Красный, Зелёный, Синий]
System.out.println(colors.size()); // 3

👤 Множество пользовательских объектов

Чтобы хранить в множестве объекты своих классов, нужно правильно реализовать два метода: equals() и hashCode(). Иначе множество будет считать два одинаковых объекта разными.

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

class Student {
    String name;
    int age;
    
    Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    // Обязательно переопределяем equals и hashCode!
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

public class Main {
    public static void main(String[] args) {
        Set<Student> students = new HashSet<>();
        students.add(new Student("Аня", 20));
        students.add(new Student("Аня", 20)); // Дубликат! Не добавится
        System.out.println(students.size()); // 1
    }
}

⚠️ Типичные ошибки при работе с множествами

1. Ожидание порядка в HashSet: HashSet не сохраняет порядок вставки. Если нужен порядок — используйте LinkedHashSet или TreeSet.
2. Изменение множества во время перебора: Нельзя удалять элементы из множества, перебирая его циклом for-each. Используйте Iterator или метод removeIf().
3. Добавление изменяемых объектов: Если объект в HashSet изменился так, что его hashCode стал другим, множество «потеряет» его.
4. Забывают переопределить equals и hashCode: Для пользовательских классов это обязательно, иначе множество не сможет обнаружить дубликаты.
5. Путают remove и removeAll: remove(x) удаляет один элемент, removeAll(set) удаляет все элементы из другого множества.
6. Добавление null в TreeSet: TreeSet не поддерживает null — будет NullPointerException.

💪 Задачи для самостоятельного решения

1. Даны два списка чисел. Найдите числа, которые встречаются в обоих списках (пересечение).
2. Дан текст. Найдите все уникальные слова и отсортируйте их по алфавиту (подсказка: используйте TreeSet).
3. У вас есть список всех студентов класса и список присутствующих сегодня. Найдите отсутствующих студентов (разность множеств).
4. Даны три множества чисел. Найдите числа, которые есть хотя бы в двух из трёх множеств.
5. Реализуйте программу, которая проверяет, является ли одно множество подмножеством другого.
6. Напишите программу, которая находит симметрическую разность двух множеств (элементы, которые есть только в одном из множеств).
7. Создайте класс «Книга» (название, автор, год). Реализуйте множество книг, где книги с одинаковым названием и автором считаются дубликатами.

✅ Итоги лекции

• Множество (Set) — это коллекция уникальных элементов.
• В Java есть три основные реализации Set: HashSet (быстрый, без порядка), LinkedHashSet (сохраняет порядок вставки), TreeSet (сортирует элементы).
• Объединение (addAll) — все элементы из обоих множеств.
• Пересечение (retainAll) — только общие элементы.
• Разность (removeAll) — элементы из первого, которых нет во втором.
• Множества идеально подходят для удаления дубликатов и быстрой проверки наличия элемента.
• Для пользовательских классов нужно переопределять equals() и hashCode().

🚀 Что дальше?

На следующих лекциях мы продолжим изучать структуры данных и коллекции:

• 📁 Файлы прямого доступа — работа с файлами на низком уровне, класс RandomAccessFile
• 🎯 Коллекции Java: Map — словари, отображения ключ-значение (HashMap, TreeMap)
• 🔗 Связанные списки — структуры данных на основе указателей
• 📊 Сравнение коллекций — когда что использовать: List, Set или Map

📚 Спасибо за внимание!

Вопросы?

← Вернуться на главную страницу