Как е реализирана структурата данни HashSet и какви принципи използва за съхраняване на елементи?

HashSet в Java е реализиран на базата на HashMap. Вътре в HashSet всеки елемент се съхранява като ключ в HashMap, а стойността е фиктивен обект-заглушка.

Основните принципи на работа на HashSet:

• Използва се хеш функция за изчисляване на хеш кода на елемента.
• Елементите се разпределят по кошници (buckets) в масив според техния хеш код.
• При колизии (същия хеш код) се използва верига или дърво за съхранение на няколко елемента.
• За проверка на наличието на елемент се използва методът equals.

По този начин HashSet осигурява бърз достъп, добавяне и премахване на елементи с амортизирана сложност около O(1).

Пример за използване:

HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
boolean hasApple = set.contains("apple"); // true