Как структура данных HashSet реализована с использованием HashMap и в чем заключается ее связь?

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

Связь:

• При добавлении элемента в HashSet он помещается как ключ в внутренний HashMap.
• Значение для ключа обычно — приватный статический объект, например PRESENT.
• Проверка наличия элемента, удаление и другие операции делегируются методам HashMap.

Пример упрощённой реализации:

public class HashSet<E> {
    private static final Object PRESENT = new Object();
    private transient HashMap<E,Object> map;

    public HashSet() {
        map = new HashMap<>();
    }

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

    public boolean contains(E e) {
        return map.containsKey(e);
    }

    public boolean remove(E e) {
        return map.remove(e) == PRESENT;
    }
}

Таким образом, HashSet использует возможности HashMap для эффективного хранения уникальных элементов без дублирования.