Java HashSet: уникальные значения, проверка вхождения и операции над множествами

Множество хранит уникальные значения

HashSet (из java.util) - это коллекция, которая хранит каждое значение не более одного раза. Здесь нет ключей и связанных с ними значений, как в HashMap - просто мешок различных элементов. Его единственная задача - быстро отвечать на один вопрос: «есть ли эта штука здесь?»

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

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // дубликат - игнорируется

        System.out.println(tags.contains("java"));     // true
        System.out.println(tags.contains("frontend")); // false
        System.out.println(tags.size());               // 2
    }
}

Здесь один параметр типа, <ElementType>. Как и с ArrayList и HashMap, переменную обычно типизируют интерфейсом Set, а конструируют HashSet.

add возвращает, было ли значение новым

add не просто сохраняет значение - он возвращает boolean, сообщающий, изменилось ли множество на самом деле. Добавление уже присутствующего значения возвращает false и оставляет множество нетронутым.

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true  - 7 было новым
        System.out.println(seen.add(7));  // false - уже есть
        System.out.println(seen);
    }
}

Это возвращаемое значение действительно полезно: if (!seen.add(x)) { /* x - повтор */ } позволяет обнаруживать дубликаты в одну строку по ходу дела.

Удаление дубликатов из списка

Поскольку множество отвергает повторы, самый быстрый способ убрать дубликаты из коллекции - сбросить её в множество. Конструктор HashSet принимает любую другую коллекцию:

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

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // каждое имя один раз
        System.out.println(unique.size());   // 3

        // нужно вернуть List?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

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

contains, remove и size

Повседневные операции повторяют операции других коллекций:

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

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

Главное преимущество перед ArrayList - это contains. Списку приходится обойти каждый элемент, чтобы ответить (O(n)); HashSet переходит к ответу почти напрямую (примерно O(1)). Когда вы замечаете, что вызываете list.contains(...) внутри цикла, обычно это сигнал переключиться на множество.

Операции над множествами: объединение, пересечение, разность

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

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // всё, что есть в любом из множеств
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // только то, что есть в обоих
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // в a, но не в b
        System.out.println(difference);   // 1 2
    }
}

Ключевая ловушка: addAll, retainAll и removeAll изменяют то множество, на котором вызваны. Именно поэтому в каждом примере a сначала копируется в новый HashSet - иначе вы уничтожили бы оригинал. Создавайте новое множество под каждый результат.

HashSet не сохраняет порядок

Как и HashMap, HashSet не гарантирует никакого порядка обхода, и порядок может различаться от запуска к запуску. Если вам нужна предсказуемость:

• LinkedHashSet сохраняет порядок вставки - порядок, в котором вы добавляли элементы.
• TreeSet держит элементы отсортированными по естественному порядку (или по Comparator, который вы зададите).

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

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

Все три реализуют интерфейс Set, так что переключение между ними - это изменение одной строки в конструкторе.

Элементы должны быть хешируемыми

HashSet под капотом опирается на HashMap, поэтому действует то же правило: он находит элементы, вычисляя их хеш, а значит, hashCode() и equals() элемента должны быть согласованы. Встроенные типы вроде String и Integer уже делают это правильно, поэтому дублирующиеся строки "java" выше корректно сливаются. Если вы храните экземпляры собственного класса, переопределите и equals, и hashCode - иначе два объекта, «равные» по смыслу, будут считаться разными, а contains и удаление дубликатов молча перестанут работать.

Далее: Обход коллекций

Теперь вы познакомились с тремя рабочими коллекциями - ArrayList, HashMap и HashSet. Каждую из них обходят немного по-разному, и есть тонкие ловушки (например, изменение коллекции во время цикла по ней). Дальше мы соберём всё воедино и разберём, как аккуратно обходить коллекции с помощью цикла for-each, итераторов и forEach.