При каком наполнении LinkedList в HashMap LinkedList преобразуется в TreeMap

Отличный вопрос! Он затрагивает важный внутренний механизм оптимизации, введенный в Java 8, и демонстрирует понимание не просто API, а работы HashMap «под капотом».

Краткий ответ: В современных реализациях HashMap (начиная с Java 8) при определенных условиях происходит не преобразование LinkedList в TreeMap, а замена односвязного списка (Node) на сбалансированное бинарное дерево (TreeNode) внутри одного и того же сегмента (bucket). Это происходит, когда количество элементов в одном bucket превышает порог TREEIFY_THRESHOLD (по умолчанию 8) И при этом общий размер HashMap достиг MIN_TREEIFY_CAPACITY (по умолчанию 64).

---

Подробное объяснение механизма

Давайте разберем этот процесс по шагам, заглянув в исходный код OpenJDK.

1. Исторический контекст: До Java 8

До Java 8 HashMap внутри каждого bucket (корзины, ячейки массива table) хранил цепочку коллизий в виде односвязного списка (Entry объектов). При большом количестве коллизий в одном bucket поиск по такому списку вырождался в O(n), что могло сильно деградировать производительность (атака HashDoS).

2. Современное решение: Java 8+

Начиная с Java 8, структура была гибридизирована:

• Пока элементов мало: используется Node<K,V> — аналог односвязного списка.
• При выполнении условий: цепочка преобразуется в TreeNode<K,V>, который является реализацией красно-черного дерева (Red-Black Tree). Это гарантирует поиск за O(log n) даже в худшем случае.

3. Ключевые константы и условия

В исходном коде java.util.HashMap определены важные константы:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Условие 1: TREEIFY_THRESHOLD = 8

Это главный порог, о котором спрашивается в вопросе. Когда в процессе добавления нового элемента (putVal) длина цепочки в bucket достигает или превышает 8, запускается проверка на возможность treeify (преобразования в дерево).

// Упрощенная логика из метода putVal
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

Условие 2: MIN_TREEIFY_CAPACITY = 64

Однако само превышение лимита в 8 элементов — недостаточное условие. В методе treeifyBin происходит дополнительная проверка:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // ЕСЛИ общий размер массива tab МЕНЬШЕ MIN_TREEIFY_CAPACITY...
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // ...то не деревефицируем, а УВЕЛИЧИВАЕМ массив (rehash)!
    else {
        // ...только ИНАЧЕ преобразуем цепочку в дерево
        // Логика преобразования Node -> TreeNode
    }
}

Зачем это нужно? Если HashMap еще маленький, эффективнее и дешевле просто увеличить размер внутреннего массива (resize()), чтобы элементы перераспределились и цепочки укоротились. Преобразование в дерево — операция более затратная по памяти и производительности, и ее применяют только к устойчиво переполненным bucket в уже большой таблице.

4. Процесс преобразования

Если оба условия выполнены:

1. Цепочка Node преобразуется в двусвязный список TreeNode (сохраняя порядок).
2. Затем этот список преобразуется в красно-черное дерево (по ключам, т.к. TreeNode содержит ссылки на родителя, левого и правого потомка).
3. Ключи (K) должны быть Comparable. Если ключи не сравнимы между собой, для определения порядка используется tieBreakOrder() (сравнение по identityHashCode).

5. Обратный процесс: UNTREEIFY_THRESHOLD = 6

Обратное преобразование (дерево -> список) происходит при удалении элементов, когда корневой узел дерева (или его потомки) становятся null или размер дерева в bucket падает ниже UNTREEIFY_THRESHOLD. Порог для обратного преобразования (6) меньше, чем для прямого (8), чтобы избежать частых переключений ("thrashing") между структурами при добавлении/удалении элементов вокруг граничного значения 7.

Почему именно 8 и 6?

Эти значения основаны на статистическом анализе и законах распределения (предполагается хорошая хэш-функция).

• При хорошем распределении вероятность достичь цепочки длиной 8 ничтожно мала (менее 1 на 10 миллионов).
• Таким образом, дерево используется только как защита от аномалий (плохих хэш-кодов или целенаправленных атак).
• Разница в 2 единицы (8 и 6) создает "гистерезис", обеспечивая стабильность состояния.

Вывод и важное уточнение терминологии

Итак, правильный ответ: HashMap преобразует цепочку коллизий из односвязного списка (Node) в красно-черное дерево (TreeNode), когда длина этой цепочки достигает TREEIFY_THRESHOLD (8) и общий размер таблицы HashMap не меньше MIN_TREEIFY_CAPACITY (64).

Обратите внимание: Не происходит преобразования в отдельную структуру данных TreeMap. Вся логика дерева инкапсулирована внутри статического вложенного класса HashMap.TreeNode. TreeMap — это самостоятельная реализация Map на основе красно-черного дерева, используемая для хранения всех элементов в упорядоченном виде, что принципиально отличается от внутренней оптимизации bucket в HashMap.