Что такое TREEIFY_THRESHOLD в HashMap?

TREEIFY_THRESHOLD в HashMap

TREEIFY_THRESHOLD — это магическое число в Java HashMap, которое определяет, при какой длине цепочки элементов (collision chain) в бакете список (LinkedList) преобразуется в сбалансированное красно-чёрное дерево (Red-Black Tree). По умолчанию это значение равно 8.

Зачем нужен TREEIFY_THRESHOLD?

В HashMap используется метод цепочек (chaining) для разрешения коллизий хеша. Когда два или более элемента имеют одинаковый хеш-код, они хранятся в одном бакете в виде связного списка. Это приводит к деградации производительности:

• LinkedList поиск: O(n) — нужно пройти по всей цепочке
• Red-Black Tree поиск: O(log n) — намного быстрее при больших количествах элементов

Как это работает?

private static final int TREEIFY_THRESHOLD = 8;
private static final int UNTREEIFY_THRESHOLD = 6;

public class HashMap<K, V> {
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
    }
    
    static class TreeNode<K, V> extends Node<K, V> {
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;
        boolean red;
    }
}

Когда в одном бакете накопится 8 элементов, HashMap автоматически преобразует список в дерево. Обратное преобразование (дерево → список) происходит при UNTREEIFY_THRESHOLD = 6, то есть когда элементов становится меньше 6.

Условия преобразования

Преобразование в дерево происходит только если:

1. Длина цепочки достигла TREEIFY_THRESHOLD (8)
2. И размер HashMap достаточен: capacity >= 64 (MIN_TREEIFY_CAPACITY)

Если capacity < 64, вместо этого происходит resize() — увеличение размера таблицы. Это предотвращает неправильные размеры buckets.

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

Эти значения выбраны эмпирически:

• 8 достаточно для минимизации ложных срабатываний (когда случайно много элементов в одном бакете)
• 6 для гистерезиса — предотвращение постоянного преобразования в обе стороны (bouncing)
• Статистически, если HashMap используется правильно, вероятность естественного достижения 8 элементов в одном бакете крайне мала

Пример на практике

HashMap<String, Integer> map = new HashMap<>();

// Допустим, все эти ключи имеют одинаковый хеш (искусственно)
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);
// ... после 8-го элемента внутренняя структура
// преобразуется из LinkedList в TreeNode<K, V>

// Теперь get() будет O(log n) вместо O(n)
Integer value = map.get("key5");

Производительность

Для n = 8: LinkedList требует в среднем 4 операции, Red-Black Tree требует ~3 операции. При n > 10 разница становится существенной.

Итого

TREEIFY_THRESHOLD = 8 — это защита от наихудшего сценария, когда много элементов попадают в один бакет из-за плохого хеша. Это делает HashMap невосприимчивым к DoS атакам, где злоумышленник специально создаёт объекты с одинаковыми хешами, чтобы деградировать производительность операций в HashMap с O(1) до O(n).