Какие знаешь ситуации, когда HashMap использует древовидную структуру для хранения элементов внутри бакетов?

HashMap и древовидные структуры внутри бакетов

В Java 8 была внедрена значительная оптимизация в HashMap. Вместо того чтобы всегда использовать linked list для разрешения коллизий, HashMap переключается на красно-чёрное дерево (Red-Black Tree) в определённых ситуациях. Это кардинально улучшило производительность при плохом распределении хэш-кодов.

Когда HashMap переходит на Tree Structure

Основной критерий — количество элементов в одном бакете: HashMap преобразует связный список в красно-чёрное дерево, когда количество элементов в одном бакете превышает TREEIFY_THRESHOLD = 8.

// Когда элементов > 8 в одном бакете
// Связный список преобразуется в TreeNode
private static final int TREEIFY_THRESHOLD = 8;

Обратное преобразование: Когда количество элементов уменьшается ниже UNTREEIFY_THRESHOLD = 6, дерево преобразуется обратно в связный список.

private static final int UNTREEIFY_THRESHOLD = 6;

Минимальный размер таблицы: Древовидная структура используется только если размер таблицы HashMap >= MIN_TREEIFY_CAPACITY = 64. Если таблица меньше, вместо перехода на дерево вызывается resize().

private static final int MIN_TREEIFY_CAPACITY = 64;

Сценарии возникновения коллизий

1. Плохой хэш-код пользовательского класса:

class BadHash {
    @Override
    public int hashCode() {
        return 1; // Все объекты имеют одинаковый хэш
    }
}

// Все элементы попадут в один бакет
HashMap<BadHash, String> map = new HashMap<>();
for (int i = 0; i < 100; i++) {
    map.put(new BadHash(), "value" + i);
}

2. Хэш-коды с низкой энтропией: Если хэш-коды сконцентрированы в определённом диапазоне, происходит неравномерное распределение по бакетам.

3. Атаки на хэш-функцию (HashDoS): Злоумышленник может специально создавать ключи с одинаковыми хэш-кодами.

Преимущества переходу на Red-Black Tree

Защита от деградации производительности:

• До Java 8 (только linked list): При коллизии поиск выполняется за O(n)
• Java 8+ (с деревом): Поиск выполняется за O(log n) даже при коллизиях

// Пример: 1000 коллизий
// С linked list: O(1000) в худшем случае
// С Red-Black Tree: O(log 1000) примерно O(10) операций

Защита от DoS атак: Древовидная структура делает атаки на хэш-функцию менее эффективными.

Практический пример

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

// При 8+ элементах в одном бакете используется дерево
for (int i = 0; i < 100; i++) {
    map.put(i * 16, "value" + i);
}

// Операции остаются O(log n) вместо O(n)
String result = map.get(50 * 16);

Детали реализации TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

Заключение

Использование красно-чёрного дерева внутри HashMap:

• Гарантирует O(log n) производительность даже при плохих хэш-функциях
• Защищает от DoS-атак на хэш-таблицы
• Сохраняет совместимость с предыдущими версиями Java

Основной сценарий активации — более 8 элементов в одном бакете при таблице размером ≥ 64.