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

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

1. Количество коллизий в одном бакете превышает TREEIFY_THRESHOLD (значение по умолчанию: 8).
2. Общее количество бакетов (capacity) в таблице не меньше MIN_TREEIFY_CAPACITY (значение по умолчанию: 64).

Почему это сделано:

• Производительность: Поиск в дереве имеет сложность O(log n) против O(n) в списке при большом количестве коллизий.
• Безопасность: Защита от атак, нацеленных на ухудшение производительности (HashDoS), путём намеренного создания коллизий.

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

Map<Integer, String> map = new HashMap<>(64); // capacity >= 64
// Генерируем ключи, попадающие в один бакет (например, с одинаковым хэшем)
for (int i = 0; i < 9; i++) {
    // Ключи, дающие коллизию. В реальности такую ситуацию сложно создать без переопределения hashCode().
    map.put(i * 64, "Value" + i);
}
// После добавления 9-го элемента в один бакет список будет преобразован в дерево.

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