Каков порог преобразования списка в дерево в HashMap?

Преобразование связного списка в красно-черное дерево в HashMap срабатывает при 8 элементах в одной корзине, но только если общий размер таблицы не менее 64 корзин.

Константы в исходном коде HashMap (Java 8+):

static final int TREEIFY_THRESHOLD = 8;    // Порог для дерева
static final int MIN_TREEIFY_CAPACITY = 64; // Минимальный размер таблицы для дерева
static final int UNTREEIFY_THRESHOLD = 6;  // Порог для обратного преобразования (дерево -> список)

Логика работы:

1. Добавление элемента: При коллизии элемент добавляется в связный список корзины.
2. Проверка порога: После добавления 8-го элемента в список проверяется capacity таблицы.
3. Решение:
   • Если capacity >= 64 → список преобразуется в дерево.
   • Если capacity < 64 → вызывается resize() для увеличения таблицы.

Пример сценария:

HashMap<String, Integer> map = new HashMap<>(16); // Начальная capacity = 16
// Симулируем коллизии: 10 элементов с одинаковым хэшем
for (int i = 0; i < 10; i++) {
    // При i=7 длина списка станет 8, но capacity=16 (<64) -> произойдет resize до 32.
    // При i=8 снова проверка, capacity=32 (<64) -> resize до 64.
    // При i=9, capacity=64 -> список наконец преобразуется в дерево.
    map.put("key" + i, i);
}

Эта двухэтапная проверка (TREEIFY_THRESHOLD + MIN_TREEIFY_CAPACITY) предотвращает преждевременное усложнение структуры в маленьких таблицах, где resize эффективнее.