Когда структура данных внутри бакета HashMap меняется на дерево

В Java 8 HashMap переходит с linked list на сбалансированное красно-черное дерево при выполнении двух условий:

1. Количество элементов в бакете превышает TREEIFY_THRESHOLD (8)
2. Общий размер HashMap превышает MIN_TREEIFY_CAPACITY (64)

Пример преобразования:

Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < 12; i++) {
    // Коллизии для одного бакета
    map.put(i * 16, "Value" + i); 
}
// При 9-м элементе в бакете происходит treeify

Преимущества:

• Поиск в дереве O(log n) вместо O(n) в списке
• Защита от DoS-атак через худший случай O(n)

Обратное преобразование (UNTREEIFY_THRESHOLD = 6) происходит при удалении элементов.