Что хранится в каждом элементе массива внутри HashMap?

Элементы массива в HashMap

HashMap в Java использует массив бакетов (buckets) для хранения данных. Каждый элемент массива (каждый бакет) содержит Node (ноду) или список нод, когда происходит коллизия хешей.

Что хранится в каждом элементе массива

Каждый элемент массива HashMap содержит:

private static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;        // Хеш-код ключа
    final K key;           // Ключ
    V value;               // Значение
    Node<K,V> next;        // Ссылка на следующий узел (для коллизий)
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Структура бакета

Каждый бакет — это либо:

1. Null — если бакет пуст
2. Одна нода (Node) — если в бакете один элемент
3. Цепочка нод — при коллизии хешей (связанный список)
4. Красно-черное дерево (TreeNode) — когда количество нод превышает threshold (обычно 8)

Пример с кодом

Когда ты добавляешь элемент в HashMap:

HashMap<String, Integer> map = new HashMap<>();
map.put("foo", 100);
map.put("bar", 200);

Внутри происходит следующее:

1. Вычисляется хеш ключа: hash = "foo".hashCode()
2. Определяется индекс бакета: index = hash % bucketSize
3. На позицию index помещается Node с данными:

Node {
  hash: -1234567890,
  key: "foo",
  value: 100,
  next: null
}

Коллизия хешей

Если два разных ключа имеют одинаковый хеш, происходит коллизия:

map.put("foo", 100);   // hash % 16 = 5, index = 5
map.put("oof", 200);   // hash % 16 = 5, index = 5 (коллизия!)

В этом случае ноды связываются в цепочку. Первая нода указывает через поле next на вторую ноду, и так далее. Это позволяет хранить несколько элементов в одном бакете.

Оптимизация: TreeNode

Начиная с Java 8, если в одном бакете накопится больше 8 элементов, HashMap преобразует цепочку в красно-черное дерево для улучшения производительности поиска:

private static class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

Ключевые параметры

• Начальная емкость (capacity): 16 по умолчанию
• Коэффициент загрузки (load factor): 0.75
• Порог преобразования в дерево (TREEIFY_THRESHOLD): 8
• Порог преобразования обратно в список (UNTREEIFY_THRESHOLD): 6

Производительность

• get(key): O(1) в среднем, O(n) в худшем случае
• put(key, val): O(1) в среднем, O(n) в худшем случае
• remove(key): O(1) в среднем, O(n) в худшем случае

В среднем O(1) благодаря хорошему распределению хешей, но в худшем случае может деградировать до O(n), если много коллизий. После преобразования в дерево — гарантировано O(log n).

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