Интерфейс Set, классы HashSet и LinkedHashSet в Java - Вопросы

Set (java.util.Set<E>) — интерфейс множества: каждый элемент хранится не больше одного раза, доступа по индексу нет. Он расширяет Collection и не добавляет новых абстрактных методов, но уточняет контракт: add() уже существующего элемента ничего не меняет и возвращает false.

Основные реализации:

• HashSet — хеш-таблица, порядок обхода не гарантирован, элементы сравниваются через hashCode() и equals();
• LinkedHashSet — хеш-таблица плюс двусвязный список, порядок вставки;
• TreeSet — хранит элементы отсортированными и сравнивает их через compareTo() или Comparator.

Кроме того, есть статические фабрики Set.of(...) (Java 9) и Set.copyOf(...) (Java 10): они создают неизменяемое множество, add() бросает UnsupportedOperationException, null запрещён, а повторяющийся аргумент в Set.of("a", "a") бросает IllegalArgumentException.

Внутри HashSet лежит HashMap: элементы множества хранятся как его ключи, а значением для всех ключей служит один общий объект-заглушка. Поэтому для элементов действуют те же правила, что для ключей HashMap, и допускается один null.

Поиск и добавление идут в два шага:

1. по hashCode() элемента вычисляется номер бакета (ячейки таблицы): (h ^ (h >>> 16)) & (capacity - 1);
2. если в бакете несколько элементов (коллизия), нужный выбирается методом equals().

Отсюда два следствия: HashSet зависит от обоих методов, а элементы обходятся в порядке бакетов — не в порядке вставки и не по возрастанию. null всегда попадает в бакет 0, а после рехеширования порядок обхода может измениться.

Контракт из документации Object:

1. пока не изменились поля, участвующие в equals(), hashCode() объекта возвращает одно и то же число (в рамках одного запуска);
2. если a.equals(b), то a.hashCode() == b.hashCode();
3. обратное неверно: одинаковые хеш-коды не означают равенства (это коллизия);
4. следовательно, при разных хеш-кодах объекты точно не равны.

Если переопределить только equals(), «равные» объекты получат разные хеш-коды из Object, попадут в разные бакеты, и equals() даже не вызовется: множество примет дубликат (size() вернёт 2), а contains() для равного объекта вернёт false.

hashCode(), возвращающий константу, контракт не нарушает, но все объекты окажутся в одном бакете и поиск станет линейным. Оба метода удобно генерировать в IntelliJ IDEA, собирать хеш через Objects.hash(...) или использовать record (Java 16), где они создаются автоматически.

initialCapacity — начальное число бакетов хеш-таблицы (по умолчанию 16). Ёмкость всегда округляется вверх до степени двойки: new HashSet<>(100) создаёт таблицу на 128 бакетов.

loadFactor — допустимая заполненность таблицы (по умолчанию 0,75). Когда число элементов становится больше capacity * loadFactor, происходит рехеширование: создаётся таблица вдвое больше, и все элементы раскладываются заново. Для 16 и 0,75 это 13-й элемент, для new HashSet<>(100) — 97-й.

Больший коэффициент экономит память, но увеличивает число коллизий; меньший ускоряет поиск ценой памяти.

Чтобы заранее выделить место ровно под N элементов, на Java 19+ используют HashSet.newHashSet(N) (для LinkedHashSet — LinkedHashSet.newLinkedHashSet(N)), а на старых версиях передают ёмкость (int) (N / 0.75f) + 1.

add(), contains() и remove() выполняются в среднем за O(1), если хеш-коды распределены равномерно. size() и isEmpty() всегда O(1): размер хранится в отдельном поле.

Худший случай — все элементы в одном бакете (например, hashCode() возвращает константу):

• до Java 8 бакет был связным списком, поиск — O(n);
• с Java 8 бакет из 8 и более элементов превращается в красно-чёрное дерево (если в таблице не меньше 64 бакетов, иначе таблица просто увеличивается), поиск — O(log n); лучше всего это работает, если элементы реализуют Comparable.

Перебор HashSet занимает время, пропорциональное сумме размера и ёмкости, потому что итератор проходит и пустые бакеты. У LinkedHashSet перебор пропорционален только размеру.

LinkedHashSet — подкласс HashSet, который внутри использует LinkedHashMap и связывает элементы двусвязным списком. Поэтому он гарантирует порядок вставки, а HashSet не гарантирует никакого порядка. Операции остаются O(1) в среднем, но каждый элемент занимает больше памяти (ссылки на предыдущий и следующий), а вставка и удаление немного медленнее.

Повторный add() существующего элемента не меняет его позицию. Типичное применение — убрать дубликаты из списка, сохранив порядок: new ArrayList<>(new LinkedHashSet<>(list)).

В Java 21 LinkedHashSet реализует SequencedSet и получил методы getFirst(), getLast(), addFirst(), addLast(), removeFirst(), removeLast() и reversed(). В отличие от add(), addFirst()/addLast() перемещают уже существующий элемент в начало или конец. Переменная должна иметь тип LinkedHashSet или SequencedSet: у Set этих методов нет.