Какой внутренний класс используется в HashMap для хранения элементов?

Ключевой класс: HashMap.Node<K,V> — базовый внутренний класс для хранения пар ключ-значение в корзинах (бакетах).

Как это работает:

1. При вызове map.put(key, value) вычисляется хэш ключа.
2. На основе хэша определяется индекс корзины.
3. В корзину помещается объект Node, содержащий ключ, значение, хэш и ссылку на следующий узел.

Пример структуры:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Для разрешения коллизий через цепочку
    // ... конструкторы и методы
}

Разрешение коллизий:

• При коллизии (одинаковый индекс корзины) узлы связываются в односвязный список.
• Если список превышает порог (TREEIFY_THRESHOLD = 8), он преобразуется в сбалансированное красно-черное дерево (класс TreeNode). Это улучшает производительность с O(n) до O(log n) в случае множества коллизий.

Практический пример добавления:

HashMap<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95); // Создается Node<String, Integer> и помещается в бакет
scores.put("Bob", 87);
// Если hash("Alice") == hash("Bob") и они попали в одну корзину,
// то Node для "Bob" будет храниться в поле `next` узла "Alice".