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

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

public class SimpleHashSet<E> {
    private static final Object PRESENT = new Object();
    private HashMap<E, Object> 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;
    }
}

Каким образом связаны структуры данных HashMap и HashSet в Java?