Java Interview Questions

Главная / Все ответы / Коллекции

Вопрос 12 · Раздел 4

Как работает HashSet внутри?

4. fastutil для примитивов 5. Treeification → индикатор плохого hashCode 6. Сериализация — custom, не стандартная

Russian Коллекции Исходный Markdown
Версии по языкам: English Russian Ukrainian

🟢 Junior Level

HashSet внутри использует HashMap!

// Внутри HashSet:
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

Как это работает:

  • Ваш элемент → ключ в HashMap
  • Значение → один и тот же объект PRESENT
  • Уникальность → HashMap не допускает дубликатов ключей

Пример:

HashSet<String> set = new HashSet<>();
set.add("A");  
// Внутри: map.put("A", PRESENT)

set.add("A");  
// Внутри: map.put("A", PRESENT) → уже есть! → false

🟡 Middle Level

Почему через HashMap?

Преимущества:
  → Один код для HashMap и HashSet
  → Все улучшения HashMap автоматически в HashSet
  → Java 8: Treeification — превращение связного списка в красно-чёрное дерево при > 8 элементов в корзине. Защита от деградации O(1) → O(n) при коллизиях hashCode.

Память

Каждый элемент в HashSet:
  HashMap$Node:
    Header: 12 байт
    int hash: 4 байта
    K key: 4-8 байт (ссылка)
    V value: 4 байта (ссылка на PRESENT)
    Node next: 4-8 байт
    Padding: до 8 байт
    
Итого: ~32 байта оверхеда на элемент!

→ HashSet<Long> в 8 раз больше, чем long[]

Коллизии и Java 8+

Мало коллизий (< 8 в корзине):
  → Связный список
  → Поиск: O(n)

Много коллизий (> 8, размер > 64):
  → Красно-черное дерево
  → Поиск: O(log n)
  
→ Защита от Hash DoS атак!

Сериализация

// Поле map = transient (не сериализуется напрямую). Причина: хеш-таблица зависит от JDK-специфичного hashCode() и рандомизации — при десериализации на другой JVM элемент попал бы в другую корзину. Вместо этого HashSet сериализует элементы и пересоздаёт map.

Ловушка: мутабельные элементы

// ❌ Потеря элемента
Person p = new Person("Ivan");
set.add(p);
p.setName("Petr");  // hashCode() изменился!
set.remove(p);      // → FALSE! Ищем не в той корзине

// ✅ Immutable элементы
record Person(String name) {}

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

  1. Нужен порядок итерации — используйте LinkedHashSet
  2. Элементы с плохим hashCode — получите O(n) вместо O(1) (множество коллизий)
  3. Храните примитивы — используйте fastutil/eclipse-collections для экономии памяти в 4 раза

🔴 Senior Level

Hash DoS Attack защита

Атака: злоумышленник подбирает ключи с одинаковым hashCode()
  → Все в одну корзину
  → Поиск O(n) вместо O(1)
  → Сервер "виснет"
  
Java 8+: Treeification при > 8 элементов
  → Поиск O(log n) даже при атаке
  → Хеш-функция с рандомизацией

Memory Deep Dive

HashSet<String> для 1 млн строк:

1 млн HashMap$Node: 32 МБ
1 млн String объектов: ~40 МБ
1 млн char[] массивов: ~24 МБ
HashMap table array: ~4 МБ

Итого: ~100 МБ

→ ArrayList<String>: ~68 МБ
→ HashSet на 50% больше!

Load Factor trade-off

По умолчанию: 0.75

Увеличить (0.9):
  → Меньше памяти
  → Больше коллизий
  → Медленнее поиск
  
Уменьшить (0.5):
  → Больше памяти
  → Меньше коллизий
  → Быстрее поиск

Альтернативы для примитивов

// ❌ HashSet<Long> для 100 млн элементов
// → 100 млн Node объектов → 3.2 ГБ!

// ✅ fastutil (открытая адресация)
LongOpenHashSet set = new LongOpenHashSet();
// → Без Node объектов → 800 МБ
// → В 4 раза меньше памяти!

Internal Structure

HashSet → AbstractSet → AbstractCollection

Делегирование:
  add(e)         → map.put(e, PRESENT)
  remove(e)      → map.remove(e) == PRESENT
  contains(e)    → map.containsKey(e)
  size()         → map.size()
  iterator()     → map.keySet().iterator()
  clear()        → map.clear()
  
→ HashSet = тонкая обёртка над keySet!

Production Experience

Реальный сценарий: Bad hashCode

  • Объекты с hashCode() = 0 для всех
  • Все в одну корзину → O(n) поиск
  • 100,000 элементов → 5 секунд на contains!
  • Решение: переписать hashCode()
  • Результат: 0.1 мс

Best Practices

  1. Элементы должны быть effectively immutable пока находятся в Set. Мутация элемента после добавления ломает hashCode/equals контракт — элемент становится «невидимым» для поиска.
  2. hashCode/equals контракт — критичен
  3. initialCapacity — избегайте ресайзов
  4. fastutil для примитивов
  5. Treeification → индикатор плохого hashCode
  6. Сериализация — custom, не стандартная

Резюме для Senior

  • HashSet = обёртка над HashMap.keySet()
  • PRESENT = static final Object заглушка
  • Memory = ~32 байта оверхеда на элемент
  • Treeification = защита от Hash DoS (> 8)
  • Transient map = custom сериализация
  • Mutable элементы = потеря данных!
  • Открытая адресация = меньше памяти (fastutil)

🎯 Шпаргалка для интервью

Обязательно знать:

  • HashSet внутри — обёртка над HashMap.keySet(), каждый элемент = ключ, значение = static final Object PRESENT
  • Сложность: O(1) для add/remove/contains в среднем случае
  • Java 8+: treeification при > 8 элементов в корзине — связный список превращается в красно-чёрное дерево (O(log n))
  • Memory overhead: ~32 байта на элемент (HashMap$Node: hash, key, value, next)
  • Load factor по умолчанию 0.75 — баланс между памятью и коллизиями
  • Сериализация custom: поле map = transient, элементы сериализуются отдельно
  • Мутабельные элементы ломают поиск — hashCode() меняется, элемент «теряется»
  • Для примитивов лучше fastutil/Trove — открытая адресация, в 4 раза меньше памяти

Частые уточняющие вопросы:

  • Зачем HashSet использует HashMap, а не свою структуру? — Переиспользование кода, все оптимизации HashMap автоматически доступны.
  • Что такое treeification и зачем нужна? — При > 8 коллизий в корзине список превращается в дерево — защита от Hash DoS атак (O(n) → O(log n)).
  • Почему сериализация custom? — Хеш-таблица зависит от JVM-специфичного hashCode() и рандомизации — при десериализации элементы могут попасть в другие корзины.
  • Как уменьшить memory footprint HashSet для примитивов? — Использовать fastutil LongOpenHashSet и аналоги — без Node-объектов, открытая адресация.

Красные флаги (НЕ говорить):

  • ❌ «HashSet хранит элементы напрямую» — хранит как ключи HashMap с заглушкой PRESENT
  • ❌ «HashSet полностью thread-safe» — нет, нужна ConcurrentHashMap или Collections.synchronizedSet
  • ❌ «HashSet гарантирует порядок итерации» — порядок не гарантирован, зависит от hashCode()
  • ❌ «Treeification происходит всегда при коллизиях» — только при > 8 элементов И размере > 64

Связанные темы:

  • [[11. В чём разница между HashSet, LinkedHashSet и TreeSet]]
  • [[14. Что такое Map и какие реализации существуют]]
  • [[15. В чём разница между HashMap, LinkedHashMap и TreeMap]]
  • [[19. Как ConcurrentHashMap обеспечивает thread-safety]]