ℹ️ Как устроен под капотом HashSet?

HashSet — это реализация множества (set), которое не допускает дублирующихся элементов. В его основе используется механизм хеширования для быстрого поиска, добавления и удаления элементов.

🔹 Хеш-таблица как основа
В основе HashSet лежит HashMap. Каждый элемент множества хранится в качестве ключа внутри объекта HashMap, а его значение всегда фиксированное — это специальный объект-заглушка. Этот объект используется для обозначения присутствия элемента, так как HashMap требует наличие пары "ключ-значение".

🔹 Хеширование
Когда вы добавляете элемент в HashSet, для него вычисляется хеш-код с помощью метода hashCode(). Этот хеш-код помогает определить, в какую "корзину" (bucket) поместится элемент. Если два элемента имеют одинаковый хеш-код (коллизия), они будут помещены в один и тот же бакет, и далее будут различаться с помощью метода equals().

🔹 Коллизии и структура бакета
До Java 8, если в бакет попадало несколько элементов (коллизия), они сохранялись в виде односвязного списка. Это приводило к тому, что в худшем случае производительность поиска и добавления элементов могла падать до O(n), если список становился слишком длинным.

С Java 8 при превышении 8 элементов в одном бакете, односвязный список преобразуется в красно-чёрное дерево, что улучшает производительность операций до O(log n). Когда количество элементов в бакете падает ниже 6, структура снова преобразуется обратно в связанный список для экономии памяти.

🔹 Добавление элементов
▪️ В среднем: добавление элемента занимает O(1), потому что благодаря хеш-кодам можно быстро находить нужную корзину для элемента.
▪️ В худшем случае: добавление элемента может занять O(n) до Java 8 (связный список) и O(log n) начиная с Java 8 (красно-чёрное дерево).

🔹 Удаление элементов
Удаление происходит также через хеш-код: ищется соответствующая корзина, а затем элемент удаляется, если он там есть. Сложность удаления аналогична добавлению: O(1) в среднем и O(n) или O(log n) в худшем случае (в зависимости от структуры бакета).

🔹 Преимущества и недостатки

▪️ Преимущества: Быстрое добавление, удаление и поиск элементов в среднем за O(1), так как используется хеширование. Улучшенная производительность с Java 8 благодаря использованию красно-чёрного дерева.
▪️ Недостатки: Не гарантирует порядок элементов, а при частых коллизиях, особенно в старых версиях Java, производительность может падать до O(n).