HashSet и интерфейс Set в Java

Если совсем коротко: HashSet это коллекция уникальных элементов. Дубликаты она молча отбрасывает, порядок не хранит, а проверка «есть такой элемент или нет» работает в среднем за O(1), сколько бы элементов внутри ни лежало. Внутри у нее обычная HashMap, где твои элементы становятся ключами. Отсюда и два главных правила: у объектов-элементов должны быть корректные equals() и hashCode(), а на порядок перебора полагаться нельзя.

Кратко

• HashSet хранит только уникальные элементы: повторный add() вернет false и ничего не добавит.
• add, remove и contains работают в среднем за O(1). «В среднем» тут важное слово: при плохих хэш-кодах все упирается в одну корзину, и с Java 8 такая корзина превращается в дерево, то есть в O(log n).
• Внутри HashSet лежит HashMap: элемент становится ключом, а значением подставляется одна и та же константа PRESENT.
• Емкость по умолчанию 16, коэффициент загрузки 0.75. Как только заполнены 75 процентов корзин, таблица удваивается и все раскладывается заново.
• null положить можно, но только один. Порядок перебора не гарантируется: нужен порядок добавления, бери LinkedHashSet, нужна сортировка, бери TreeSet.
• Уникальность считается по hashCode() и equals(). Забыл переопределить их в своем классе, и два одинаковых по данным объекта окажутся в множестве оба.

Помнишь, как в детстве собирал коллекцию марок или вкладышей от жвачек? И как бесило, когда попадалась одна и та же картинка в десятый раз? Вот HashSet это такая коллекция в Java, которая автоматически отсеивает все повторы. Добавляешь элемент второй раз, и он просто проигнорируется. Удобно же! Я когда только начинал изучать коллекции, думал: "Ну ладно, есть ArrayList, зачем мне еще что-то?" А потом столкнулся с задачей: нужно было собрать список уникальных email'ов из базы данных. И тут-то я понял всю красоту HashSet. Вместо того чтобы городить проверки "а есть ли уже такой элемент", просто кидаешь все в HashSet и получаешь готовый список уникальных значений.

Что такое HashSet и почему он крутой

HashSet это класс из Java Collections Framework, который реализует интерфейс Set. А Set, если по-простому, это математическое множество. Помнишь из школы круги Эйлера? Вот это оно и есть. Главные фишки HashSet: Только уникальные элементы. Попробуй добавить один и тот же элемент дважды, и второй раз он просто не добавится. Причем HashSet сам следит за уникальностью, тебе ничего проверять не нужно. Скорость огонь. Добавить, удалить или проверить наличие элемента можно за константное время O(1). Это значит, что неважно, сколько у тебя элементов, 10 или 10 миллионов, операция выполнится примерно за одно и то же время. Круто, да? Одну оговорку тут все же держи в голове. Документация обещает константное время «при условии, что хэш-функция раскидывает элементы по корзинам равномерно». Если hashCode() у твоего класса возвращает всем объектам одно и то же, все они улягутся в одну корзину, и никакого O(1) не будет. Правда, с Java 8 совсем катастрофы не случится: когда в одной корзине набирается 8 элементов, а таблица доросла до 64 корзин, список внутри корзины превращается в красно-черное дерево, и худший случай получается O(log n), а не O(n). Можно хранить null. В отличие от некоторых других коллекций, HashSet спокойно принимает null-значения. Правда, только одно, ведь это тоже элемент, а значит должен быть уникальным. Порядок не гарантируется. И вот тут многие новички спотыкаются. Добавил элементы в одном порядке, а при переборе получил в другом. Это нормально! HashSet вообще не заморачивается с порядком, он думает только об эффективности.

Как это работает под капотом

Вот это самое интересное. Оказывается, HashSet это такая хитрая обертка над HashMap. Да-да, внутри у него настоящая HashMap! Когда ты добавляешь элемент в HashSet, на самом деле происходит вот что:

• твой элемент становится ключом в HashMap;
• а в качестве значения подставляется одна и та же константа PRESENT.

Представь себе гардероб с номерками. Ты сдаешь куртку (твой элемент) и получаешь номерок (это будет ключ). А все куртки висят на одинаковых плечиках (константа PRESENT). Гардеробщику важны только номерки, они все разные. А плечики одинаковые, но это никого не волнует. Вот как это выглядит в исходниках Java:

private transient HashMap<E,Object> map;

// Эта константа используется как "заглушка" для всех значений
private static final Object PRESENT = new Object();

// Когда добавляешь элемент в HashSet
public boolean add(E e) {
    // На самом деле добавляешь его как ключ в HashMap
    return map.put(e, PRESENT) == null;
}

Видишь? Метод add() просто вызывает put() у внутренней HashMap, подставляя твой элемент как ключ и константу PRESENT как значение. Кстати, именно поэтому в документации к HashSet часто упоминается хэш-таблица. Потому что он использует HashMap, а HashMap построена на хэш-таблице.

История про коэффициент загрузки (она важная!)

Когда я впервые увидел конструктор HashSet с параметрами initialCapacity и loadFactor, я подумал: "Зачем мне это? Я просто хочу хранить элементы!" Но потом на одном проекте наш HashSet начал тормозить, и вот тогда я разобрался. Начальная емкость (initial capacity) это сколько "ячеек" изначально создается в твоей хэш-таблице. По умолчанию их 16. Представь себе комод с 16 ящиками. Коэффициент загрузки (load factor) это такой порог, при достижении которого комод "расширяется". По умолчанию он равен 0.75 (или 75%). Вот как это работает на примере. У тебя есть комод на 16 ящиков. Коэффициент загрузки 0.75. То есть когда 12 из 16 ящиков заполнятся (16 умножить на 0.75 будет как раз 12), комод вдруг БАЦ! и расширяется до 32 ящиков. А все содержимое перераспределяется заново. Это называется красивым словом "ре-хэширование". А зачем расширяться заранее, спросишь ты? Ну подумай сам: если ждать, пока все ящики забьются до отказа, начнутся проблемы. Элементы начнут "сталкиваться" друг с другом это называется коллизиями. И вместо супербыстрой работы за O(1) получишь медленный O(n). А это уже совсем не весело. Формула простая:

Коэффициент загрузки = Количество элементов / Размер хэш-таблицы

Подставляем наши числа: 12 элементов делим на 16 ячеек = 0.75. Все сходится! И тут всегда возникает вопрос: а почему именно 0.75, а не 0.5 или 0.9? Честно говоря, это эмпирически подобранное значение, компромисс между скоростью и памятью. Если поставить 0.5, коллизий будет меньше, но половина памяти просто пропадет зря. Если накрутить до 0.9, память использоваться будет эффективнее, зато коллизий будет хоть отбавляй. Вот и выбрали золотую середину.

Конструкторы HashSet

Когда создаешь HashSet, можешь выбрать один из нескольких вариантов. Самый простой:

HashSet<String> set1 = new HashSet<>();

Тут все по умолчанию: емкость 16, коэффициент 0.75. Для большинства задач этого хватает с головой. Но бывает, что ты заранее знаешь: элементов будет много. Тогда можешь сразу задать бóльшую емкость:

HashSet<String> set2 = new HashSet<>(100);

Коэффициент останется стандартным 0.75, а вот начальный размер будет уже не 16. Строго говоря, ровно 100 корзин ты не получишь: размер таблицы всегда степень двойки, поэтому 100 округлится вверх до 128. Смысл от этого не меняется, лишних расширений на старте не будет. Только не увлекайся: документация HashSet предупреждает, что перебор занимает время, пропорциональное числу корзин, так что слишком большая емкость замедлит именно перебор. Хочешь контролировать и емкость, и коэффициент? Пожалуйста:

HashSet<String> set3 = new HashSet<>(100, 0.9f);

Правда, я обычно коэффициент не трогаю: ребята из Oracle не дураки, 0.75 выбрали неспроста. А вот что реально удобно это создать HashSet из готовой коллекции:

List<String> list = Arrays.asList("Java", "Python", "Java", "C++");
HashSet<String> set4 = new HashSet<>(list);

Дубликаты отфильтруются сами собой! Я этим трюком постоянно пользуюсь, когда надо быстренько почистить список от повторов. И еще один способ, про который мало кто знает, потому что он совсем свежий. С Java 19 у HashSet есть статическая фабрика newHashSet():

HashSet<String> set5 = HashSet.newHashSet(100);

Разница с new HashSet<>(100) принципиальная. Там ты задаешь размер таблицы, а тут говоришь, сколько элементов собираешься положить. Емкость метод подберет сам, с запасом под коэффициент 0.75, чтобы расширений при заполнении не случилось вообще. То есть больше не нужно в уме делить на 0.75 и округлять вверх до степени двойки: за тебя это сделает документированная фабрика. Такие же newHashMap, newLinkedHashSet и newLinkedHashMap появились тогда же.

Практический пример

Ладно, хватит теории. Давай посмотрим живой код:

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {
        HashSet<String> countries = new HashSet<>();
        
        // Добавляем страны
        countries.add("Польша");
        countries.add("Чехия");
        countries.add("Франция");
        countries.add("Польша"); // Попытка добавить дубликат
        
        // Смотрим, что получилось
        System.out.println("Страны: " + countries);
        System.out.println("Количество: " + countries.size());
        
        // Проверяем наличие элемента
        if (countries.contains("Франция")) {
            System.out.println("Франция в списке!");
        }
        
        // Удаляем элемент
        countries.remove("Чехия");
        System.out.println("После удаления: " + countries);
        
        // Перебираем элементы
        System.out.println("\nПеребор всех элементов:");
        for (String country : countries) {
            System.out.println("- " + country);
        }
    }
}

Вывод:

Страны: [Франция, Чехия, Польша]
Количество: 3
Франция в списке!
После удаления: [Франция, Польша]

Перебор всех элементов:
- Франция
- Польша

Видишь? "Польша" попала в множество только один раз, хотя мы пытались запихнуть ее туда дважды. А порядок вывода получился вообще обратным порядку добавления: клали Польшу, Чехию и Францию, а на выходе Франция, Чехия, Польша. Для HashSet это абсолютно нормально. Он раскладывает элементы по корзинам, номер которых считается из хэш-кода строки, и обходит потом корзины по порядку номеров, а не по порядку добавления.

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

Метод add(E e) добавляет элемент, но только если такого еще нет. Возвращает true, когда элемент реально добавился, и false, если он уже был. Это удобно для проверок. remove(Object o) удаляет элемент. Тоже возвращает true или false в зависимости от того, был ли элемент в множестве. С помощью contains(Object o) можно проверить, есть ли элемент. Работает моментально, за O(1). Это одна из главных фишек HashSet! Метод size() просто говорит, сколько элементов внутри. Есть еще isEmpty() проверяет, пусто ли множество. А clear() вычищает все подчистую. Через iterator() получаешь итератор, чтобы пройтись по всем элементам. Хотя обычно проще использовать for-each цикл. И наконец clone() делает копию множества. Но учти, это поверхностная копия: сам HashSet новый, а вот элементы внутри остаются те же самые объекты.

HashSet и многопоточность (важная тема!)

Вот тут многие попадаются. HashSet НЕ является потокобезопасным! Если несколько потоков одновременно пытаются изменить HashSet, может случиться что угодно, от потерянных данных до падения программы. В старых статьях часто рекомендуют использовать Collections.synchronizedSet():

Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());

Но есть проблема: этот метод блокирует всю коллекцию целиком для любой операции. Это медленно и неэффективно. Один поток читает, все остальные ждут. Другой поток добавляет, опять все ждут. Современный подход (Java 8+):

// Создаем потокобезопасный Set на основе ConcurrentHashMap
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();

Или так:

Set<String> concurrentSet = Collections.newSetFromMap(
    new ConcurrentHashMap<>()
);

ConcurrentHashMap использует куда более умную систему блокировок. Читатели не блокируются вообще никогда, документация формулирует это прямо: операции чтения блокировок не требуют, и заблокировать всю таблицу целиком нельзя в принципе. А пишущий поток захватывает не коллекцию, а всего одну корзину. Кстати, если тебе где-то попадется объяснение «блокируются отдельные сегменты», знай, что оно про Java 7. В Java 8 класс переписали, сегменты убрали совсем: добавление в пустую корзину делается атомарной операцией CAS, а если корзина занята, то synchronized вешается на первый узел именно этой корзины. Параметр concurrencyLevel в конструкторе остался, но сегодня это просто подсказка о размере, оставленная ради совместимости. Если тебе нужен именно отсортированный потокобезопасный Set, тогда используй ConcurrentSkipListSet. Но учти, что операции там будут O(log n) вместо O(1), потому что внутри древовидная структура.

Частые вопросы (FAQ)

Если я удалю элемент из середины HashSet, останется ли "дырка"?

Сам вопрос немного не про то: у HashSet нет ни индексов, ни порядка, так что никакой «середины» в нем не существует. Снаружи ты дырку и не увидишь: size() уменьшится, перебор удаленный элемент пропустит. А вот внутри все интереснее. HashSet живет на массиве корзин, и после удаления корзина просто становится пустой. Никто ничего не «схлопывает», и таблица обратно не сжимается: емкость умеет только расти. Схлопывание элементов со сдвигом индексов это про ArrayList, а не про HashSet.

Зачем нужен коэффициент загрузки, если можно просто увеличивать размер, когда места не хватает?

Все дело в коллизиях! Если подождать, пока заполнятся все 100% ячеек, коллизий будет очень много. Это сильно замедлит работу. Расширяясь на 75% заполненности, мы сохраняем баланс между скоростью и памятью.

Почему порядок элементов в HashSet такой странный?

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

Что будет, если я создам свой класс, засуну объекты в HashSet, но забуду переопределить equals() и hashCode()?

Все сломается! HashSet определяет уникальность элементов именно через hashCode() и equals(). Если не переопределишь эти методы, даже объекты с одинаковыми данными будут считаться разными. Это классическая ошибка новичков, и разобрана она подробно в статье про equals и hashCode.

А можно использовать HashSet для хранения массивов?

Технически можно, но это плохая идея. У массивов equals() и hashCode() работают не так, как ты ожидаешь: они сравнивают ссылки, а не содержимое. Лучше используй List или преобразуй массивы в списки через Arrays.asList().

Что будет, если изменить объект уже после того, как он попал в HashSet?

Ты его потеряешь. Номер корзины вычисляется из хэш-кода в момент добавления. Если поменять поле, которое участвует в hashCode(), элемент останется лежать в старой корзине, а contains() пойдет искать его в новой и вернет false. При этом элемент никуда не делся: size() его считает, перебор его показывает, а удалить через remove() уже не выйдет. Отсюда простое правило: объекты для HashSet лучше делать неизменяемыми хотя бы по тем полям, что участвуют в hashCode().

Почему HashSet быстрее, чем проверка через ArrayList.contains()?

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

Когда использовать HashSet

HashSet это твой выбор, если нужна коллекция уникальных элементов и важна скорость. Особенно если часто проверяешь, есть ли элемент в коллекции, тут HashSet рвет всех. А порядок не важен? Вообще идеально! А вот если порядок критичен, тогда бери LinkedHashSet (он сохранит порядок добавления) или TreeSet (отсортирует автоматически). Работаешь с несколькими потоками одновременно? Забудь про обычный HashSet, юзай ConcurrentHashMap.newKeySet(). Ну а если тебе вообще нужны дубликаты, то это уже не Set, а List. Чтобы не держать это в голове, вот три набора рядом:

Практика это наше все

Знаешь, можно прочитать про коллекции десять статей, но настоящее понимание придет только когда сам напишешь код. Попробуй вот что: напиши программу, которая берет текст (любой, хоть "Преступление и наказание") и находит все уникальные слова. Используй HashSet для хранения. А потом, чисто ради интереса, попробуй сделать то же самое, но с ArrayList, где ты руками проверяешь через contains(), есть ли слово или нет. Запусти на большом тексте и сравни время работы. Охренеешь от разницы, честно! Коллекции в Java это фундамент. Без них никуда. Так что время, потраченное на их изучение, точно не пропадет зря!

Читайте также

• Коллекции в Java: Java Collections Framework
• HashMap и Map в Java
• List в Java
• Топ 10 вопросов о коллекциях в Java