Как хранится значение, которое из HashSet попадает в HashMap

Хранение значений из HashSet в HashMap

Этот вопрос касается внутреннего устройства hash-based коллекций в Java и того, как они обрабатывают элементы.

1. Как устроен HashSet

HashSet — это просто обёртка над HashMap:

public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

Важно: HashSet хранит элементы как ключи в HashMap, а в качестве значения всегда PRESENT (фиксированный объект).

2. Как хранится элемент в HashMap

Когда ты добавляешь элемент в HashMap (или HashSet через него):

HashMap<String, Integer> map = new HashMap<>();
map.put("John", 25);

HashSet<String> set = new HashSet<>();
set.add("John");

Процесс хранения:

1. Вычислить hash-код ключа
2. Определить позицию в массиве bucket'ов
3. Если collision, использовать linked list или red-black tree
4. Хранить Entry с полями: key, value, hash

3. Структура узла в HashMap

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

4. Red-Black Tree в HashMap (Java 8+)

Если в одном bucket'е более 8 элементов, LinkedList преобразуется в красно-чёрное дерево — ускоряет поиск с O(n) до O(log n).

5. Load Factor и rehashing

HashMap<String, Object> map = new HashMap<>(16, 0.75f);

// Когда size > 16 * 0.75 = 12 элементов
// HashMap создаёт новый массив размером 32

Итого

• HashSet использует HashMap: элементы = ключи
• Значение всегда PRESENT: фиксированный объект
• Хранение: в массиве bucket'ов через hash-код
• Collision resolution: linked list или red-black tree
• Rehashing: при превышении load factor