Java HashSet

HashSet<E> — это реализация, которую выбирают в первую очередь, когда нужно множество. Она основана на хеш-таблице — внутри это HashMap с фиктивным значением — поэтому add, remove и contains работают за ожидаемое O(1): стоимость равна вычислению хеша элемента плюс одна-две проверки равенства, независимо от количества уже находящихся в множестве элементов. Именно это свойство делает хеш-множества правильным ответом на вопросы «видел ли я это раньше?», при дедупликации и любой проверке принадлежности, которая была бы квадратичной для List.

Что на самом деле означает «почти константное время»

Константное время не бесплатно; оно амортизировано. Каждая операция выполняет примерно следующее:

1. Вычислить e.hashCode(). Перемешать старшие и младшие биты, чтобы хеш вроде 0x...0000 не схлопнулся в корзину 0.
2. Найти корзину по индексу bucketIndex = hash & (table.length - 1).
3. Пройти связанную цепочку корзины (или, начиная с Java 8, небольшое сбалансированное дерево, если цепочка стала длинной), вызывая equals, пока не найдёт элемент или не дойдёт до конца.

Шаг 3 — место, где стоимость растёт, если hashCode плохой. При разумном хеше цепочка состоит из одного-двух элементов; при константном хеше — из всех когда-либо вставленных элементов. Это разница между O(1) и O(n) на операцию.

Ёмкость, коэффициент загрузки и перехеширование

HashSet имеет резервный массив корзин. Два параметра конструктора управляют им:

• Начальная ёмкость — начальное количество корзин. По умолчанию 16. Округляется до степени двойки.
• Коэффициент загрузки — отношение числа элементов к числу корзин, при котором таблица удваивается в размере. По умолчанию 0.75.

Когда size / capacity превышает коэффициент загрузки, множество перехешируется: выделяется новый массив вдвое большего размера, и каждый элемент перераспределяется по корзинам. Перехеширование — O(n): именно эта стоимость амортизируется по O(1) вставкам перед ним. Предварительное задание размера для множества, которое будет содержать ~1 000 000 элементов, избавляет от двадцати удвоений:

Set<Long> ids = new HashSet<>(1_500_000); // skip the doublings up to ~1M

Меньшие коэффициенты загрузки (например, 0.5) расходуют больше памяти, но уменьшают коллизии; большие (например, 0.9) упаковывают плотнее, но удлиняют цепочки. Значение по умолчанию 0.75 — баланс, откалиброванный Sun десятилетия назад, и он по-прежнему актуален — не трогайте его без бенчмарка.

Null, порядок, потокобезопасность

Три правила:

1. Один элемент null разрешён. HashSet хранит его в корзине 0 с особым хешем 0. Это намеренное удобство — Map.of/Set.of и TreeSet оба запрещают null.
2. Порядок итерации не гарантируется. Порядок меняется при перехешировании таблицы и не является стабильным даже между JVM. Если нужен порядок вставки, используйте LinkedHashSet; если нужна сортировка, используйте TreeSet.
3. Не потокобезопасен. Параллельная мутация повредит структуру. Для многопоточного кода используйте ConcurrentHashMap.newKeySet() (представление Set параллельной map) или оберните в Collections.synchronizedSet.

hashCode — ваша ответственность

Помещение собственного класса в HashSet работает только при условии корректного переопределения hashCode и equals согласованно. Контракт из Object:

• Если a.equals(b), то a.hashCode() == b.hashCode().
• Если a.hashCode() == b.hashCode(), a.equals(b) может быть false (коллизия).

Нарушение первой части контракта — наиболее распространённая причина ошибок «я добавил, но contains возвращает false». Современные IDE и ключевое слово record генерируют оба метода автоматически — используйте их.

record Tag(String name) {}            // hashCode/equals auto-generated
Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
System.out.println(tags.contains(new Tag("java"))); // true

Ловушка изменяемых элементов

Более тонкая ошибка: хранение объекта, чей hashCode зависит от изменяемых полей, с последующей мутацией после вставки. Хеш, определивший корзину для элемента, был вычислен в момент вставки; как только вы измените поле, от которого зависит хеш, объект окажется в «неправильной» корзине, и contains просматривает цепочку, которая не включает его — даже если это та же самая ссылка.

class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) {
        return o instanceof Box b && b.n == n;
    }
    @Override public int hashCode() { return Integer.hashCode(n); }
}

Box box = new Box(1);
Set<Box> set = new HashSet<>();
set.add(box);
box.n = 2;                  // mutate a field hashCode depends on
System.out.println(set.contains(box)); // false — element is now in the wrong bucket

Заметьте, что это проявляется только когда hashCode читает изменяемое состояние. StringBuilder, например, использует хеширование по идентичности, поэтому его мутация никогда не перемещает объект между корзинами — но полагаться на это ненадёжно. Решение не в хитрости; оно в том, чтобы помещать в хеш-множества неизменяемые элементы. String, Integer, ваши собственные record-ы, свежесохранённые DTO. Если нужно множество, ключом которого служит изменяемое состояние, используйте его неизменяемую проекцию.

Развёрнутый пример: дедупликация, проверка принадлежности и ёмкость

Программа ниже демонстрирует четыре причины, по которым выбирают HashSet: дедупликация, быстрые проверки принадлежности, операции над множествами и стоимость плохого hashCode.

Что стоит запомнить:

• Цикл дедупликации работает за O(n) — каждый add занимает константное время, а итоговый unique.size() равен количеству уникальных входных данных.
• contains в множестве из 1 000 000 элементов вернул результат за микросекунды. Вот почему HashSet — инструмент проверки принадлежности в JDK.
• Запись Tag получает equals/hashCode бесплатно, поэтому два объекта Tag("java") схлопываются в один элемент.
• Пример с Box — это ловушка: тот же объект, мутированный после вставки так, что его hashCode изменился, теперь возвращает contains(box) == false. Помещайте в хеш-множества неизменяемые элементы.

Что дальше

HashSet не гарантирует никакого порядка итерации. Если нужно запоминать порядок вставки элементов — например, при построении списка тегов, где пользователь ожидает увидеть теги в порядке добавления, — подходящим инструментом является LinkedHashSet. Это следующая глава.

Практика