Какую роль играет красно-черное дерево в HashMap (Java 8+)?

В HashMap (начиная с Java 8) красно-черное дерево (Red-Black Tree) используется для оптимизации обработки коллизий. Когда слишком много ключей попадает в одну корзину (bucket), вместо односвязного списка эта корзина преобразуется в сбалансированное красно-черное дерево.

Цель: Преодолеть худший случай O(n) для операций в списке, обеспечив логарифмическую сложность O(log n) для get(), put() и remove() даже при множестве коллизий.

Условия преобразования:

• Список -> Дерево: Когда длина цепочки в корзине достигает порога TREEIFY_THRESHOLD (по умолчанию = 8) и общее количество корзин в таблице не меньше MIN_TREEIFY_CAPACITY (по умолчанию = 64).
• Дерево -> Список: Когда количество узлов в дереве уменьшается до UNTREEIFY_THRESHOLD (по умолчанию = 6).

Что хранит узел дерева (TreeNode)? Каждый TreeNode расширяет Node и содержит:

• Стандартные поля Entry: hash, key, value, next (для обратной совместимости).
• Ссылки для организации дерева: parent, left, right.
• Флаг boolean red для поддержания инвариантов красно-черного дерева (балансировка).

Пример структуры (упрощенно):

// Внутри HashMap
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // Родительский узел
    TreeNode<K,V> left;    // Левый потомок
    TreeNode<K,V> right;   // Правый потомок
    TreeNode<K,V> prev;    // Предыдущий узел (для отмены преобразования)
    boolean red;           // Цвет узла
    // ... методы балансировки, поиска и т.д.
}

Итог: Это внутренняя оптимизация, которая делает HashMap устойчивым к атакам, вызывающим большое количество коллизий, и сохраняет его производительность в неблагоприятных сценариях.