Что находится под капотом в качестве структуры у HashSet

HashSet внутренняя реализация - Делегирование HashMap

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

Архитектура HashSet

HashSet внутри:
┌──────────────────────────────┐
│ HashSet<String>              │
├──────────────────────────────┤
│ private HashMap<E, Object>   │
│         map                  │
│                              │
│ private static final Object  │
│         PRESENT = new Object()
└──────────────────────────────┘
        │
        └─→ Делегирует все операции в HashMap

Исходный код HashSet

public class HashSet<E> extends AbstractSet<E> implements Set<E> {
    
    // Внутренний HashMap
    private transient HashMap<E, Object> map;
    
    // Фиксированный объект в качестве значения
    private static final Object PRESENT = new Object();
    
    // Конструктор
    public HashSet() {
        map = new HashMap<>();
    }
    
    // Методы HashSet просто делегируют HashMap
    
    @Override
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
        // put возвращает null если ключа не было (новый элемент)
        // put возвращает старое значение если ключ существовал (дубликат)
    }
    
    @Override
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
        // remove возвращает значение, которое было связано с ключом
    }
    
    @Override
    public boolean contains(Object o) {
        return map.containsKey(o);
        // Просто проверяет наличие ключа в HashMap
    }
    
    @Override
    public int size() {
        return map.size();
    }
    
    @Override
    public void clear() {
        map.clear();
    }
    
    @Override
    public Iterator<E> iterator() {
        return map.keySet().iterator();
        // Итератор на ключах HashMap
    }
}

Как работает добавление элемента

HashSet<String> set = new HashSet<>();

// Что происходит при set.add("Alice")?
set.add("Alice");

// 1. Вызывается HashMap.put("Alice", PRESENT)
// 2. HashMap вычисляет хеш "Alice"
// 3. HashMap ищет элемент по хешу
// 4. Если "Alice" не существует в HashMap:
//    - Добавляется новая запись (Alice → PRESENT)
//    - put возвращает null
//    - HashSet.add() возвращает true ✓
// 5. Если "Alice" уже существует:
//    - put возвращает старое значение (PRESENT)
//    - HashSet.add() возвращает false ✗ (уже в наборе)

Практический пример

public class HashSetBehavior {
    
    public static void main(String[] args) {
        HashSet<String> fruits = new HashSet<>();
        
        // Добавление элементов
        System.out.println(fruits.add("Apple"));    // true - добавлено
        System.out.println(fruits.add("Banana"));   // true - добавлено
        System.out.println(fruits.add("Apple"));    // false - дубликат
        
        // Что на самом деле в HashMap:
        // HashMap.put("Apple", PRESENT)
        // HashMap.put("Banana", PRESENT)
        // HashMap.put("Apple", PRESENT) → обновляет, не добавляет
        
        System.out.println(fruits.size());  // 2
        System.out.println(fruits.contains("Apple"));  // true
        
        // Итерация работает на ключах HashMap
        for (String fruit : fruits) {
            System.out.println(fruit);  // Apple, Banana
        }
    }
}

Сложность операций

// Благодаря использованию HashMap, операции имеют:
// add(E e):        O(1) в среднем
// remove(Object o): O(1) в среднем
// contains(Object): O(1) в среднем
// size():          O(1)
// iterator():      O(1) начало, O(n) полный проход

Визуальное представление памяти

HashSet<String> set = new HashSet<>();
set.add("Alice");
set.add("Bob");
set.add("Charlie");

Внутренняя структура:
┌──────────────────────────────────────┐
│ HashSet                              │
│ ┌──────────────────────────────────┐ │
│ │ map: HashMap<String, Object>     │ │
│ │ ┌────────────────────────────────┤ │
│ │ │ Buckets Array (16)             │ │
│ │ ├────────────────────────────────┤ │
│ │ │[0] → null                      │ │
│ │ │[1] → (Alice → PRESENT)         │ │
│ │ │[2] → (Bob → PRESENT)           │ │
│ │ │[3] → null                      │ │
│ │ │[7] → (Charlie → PRESENT)       │ │
│ │ │...                             │ │
│ │ │[15] → null                     │ │
│ │ └────────────────────────────────┘ │
│ └──────────────────────────────────┘ │
└──────────────────────────────────────┘

LinkedHashSet - вариация

// LinkedHashSet расширяет HashSet с сохранением порядка
public class LinkedHashSet<E> extends HashSet<E> {
    
    // Использует LinkedHashMap вместо HashMap
    // LinkedHashMap = HashMap + двусвязный список для порядка
    
    // Результат: сохранение порядка вставки
    LinkedHashSet<String> set = new LinkedHashSet<>();
    set.add("C");
    set.add("A");
    set.add("B");
    
    // Итерация: C, A, B (в порядке вставки)
    for (String s : set) System.out.println(s);
}

TreeSet - отдельная реализация

// TreeSet НЕ использует HashMap!
// Вместо этого использует TreeMap (красно-чёрное дерево)

public class TreeSet<E> extends AbstractSet<E> {
    
    private transient NavigableMap<E, Object> map;
    private static final Object PRESENT = new Object();
    
    // Результат: элементы хранятся в отсортированном порядке
    // Операции: O(log n) вместо O(1)
    
    TreeSet<String> set = new TreeSet<>();
    set.add("C");
    set.add("A");
    set.add("B");
    
    // Итерация: A, B, C (в отсортированном порядке)
    for (String s : set) System.out.println(s);
}

Почему HashSet так реализован?

Преимущества переиспользования HashMap:

1. DRY принцип — не дублируется логика хеширования и управления бакетами
2. Производительность — HashMap уже оптимизирован (Java 8 использует деревья)
3. Совместимость — если HashMap обновляется, HashSet получает улучшения автоматически
4. Простота — код HashSet очень короткий и понятный

Минусы:

1. Память — каждый элемент занимает место на значение (PRESENT объект)
2. Наследование — HashSet наследует от AbstractSet, что добавляет слой абстракции

HashSet демонстрирует классический паттерн Adapter (Адаптер) — оборачивает HashMap в интерфейс Set.