Какова внутренняя реализация HashSet в Java?

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

Упрощенная схема из исходного кода OpenJDK:

public class HashSet<E> {
    private transient HashMap<E, Object> map;
    // Фиктивное значение для ассоциации с каждым ключом
    private static final Object PRESENT = new Object();

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

    public boolean add(E e) {
        // Успешное добавление, если ключа ранее не было (put возвращает null)
        return map.put(e, PRESENT) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

Следствия этой реализации:

• Производительность: Операции add, remove, contains выполняются за амортизированное O(1), как у HashMap.
• Порядок элементов: Не гарантируется (зависит от хэш-функции и размера таблицы). Используйте LinkedHashSet для сохранения порядка вставки.
• Дубликаты: HashSet не позволяет дубликаты, так как HashMap не позволяет дубликаты ключей.
• Null: Разрешает один элемент null, так как HashMap разрешает один ключ null.
• Итерация: Итератор по HashSet проходит по ключам внутренней HashMap.