При каких условиях связный список в HashMap преобразуется в дерево?

В Java 8+ HashMap оптимизирует обработку коллизий, преобразуя связный список в красно-черное дерево при одновременном выполнении двух условий:

1. Длина списка в одной корзине (bucket) достигает значения TREEIFY_THRESHOLD (по умолчанию 8 элементов).
2. Общее количество корзин в HashMap (capacity) равно или превышает MIN_TREEIFY_CAPACITY (по умолчанию 64).

Если capacity < 64, при достижении длинного списка произойдет resize() (удвоение размера таблицы) вместо преобразования в дерево.

Пример, инициирующий преобразование:

// Ключи с одинаковым хэш-кодом попадают в одну корзину
class BadKey {
    int id;
    @Override
    public int hashCode() { return 1; } // Постоянная коллизия
}

HashMap<BadKey, String> map = new HashMap<>();
// Добавляем 9 элементов в одну корзину
for (int i = 0; i < 9; i++) {
    map.put(new BadKey(i), "Value" + i);
    // После 8-го элемента, если размер таблицы >= 64,
    // список в корзине станет деревом.
}

Обратное преобразование (дерево -> список) происходит при уменьшении количества элементов в узле дерева до UNTREEIFY_THRESHOLD (по умолчанию 6).

Зачем это нужно? Преобразование снижает сложность поиска в корзине с коллизиями с O(n) до O(log n).