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

Внутренняя структура HashMap в Java эволюционировала для решения проблемы "злонамеренных" или неудачных хэш-функций. Изначально каждый бакет (ячейка массива) представлял собой односвязный список. При возникновении коллизий (когда разные ключи имеют одинаковый индекс бакета) элементы добавлялись в этот список. В нормальных условиях это работает быстро, но если хэш-функция возвращает много одинаковых индексов, список в одном бакете может стать очень длинным. Поиск в таком списке имеет сложность O(n), что может серьёзно замедлить работу коллекции.

Переход от списка к дереву

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

• Количество элементов в одном бакете превышает константу TREEIFY_THRESHOLD (значение по умолчанию — 8).
• Общее количество бакетов в HashMap не меньше MIN_TREEIFY_CAPACITY (значение по умолчанию — 64). Второе условие нужно, чтобы избежать преждевременного создания дерева при маленьком размере таблицы, когда её лучше просто увеличить (rehash).

После преобразования операции поиска, вставки и удаления в этом бакете выполняются за O(log n), где n — количество элементов в дереве. Это значительно лучше O(n) для длинного списка.

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

Рассмотрим ситуацию, которая может спровоцировать преобразование. Для этого создадим ключи с плохим хэш-кодом, чтобы они попадали в один бакет.

import java.util.HashMap;

class BadKey {
    int id;
    // Намеренно плохой хэш-код — всегда возвращает 1
    @Override
    public int hashCode() { return 1; }
    @Override
    public boolean equals(Object o) { /* сравнение по id */ }
}

public class HashMapTreeExample {
    public static void main(String[] args) {
        HashMap map = new HashMap<>();
        // Вставляем более 8 элементов с одинаковым хэш-кодом
        for (int i = 0; i < 10; i++) {
            BadKey key = new BadKey();
            key.id = i;
            map.put(key, "Value" + i);
        }
        // При достаточном размере таблицы бакет с индексом 1
        // превратится из списка в красно-чёрное дерево.
        System.out.println(map.size());
    }
}

В реальных приложениях такие ключи встречаются редко, но эта защита критически важна для устойчивости к атакам, когда злоумышленник может специально генерировать ключи с коллизиями, чтобы замедлить сервис (атака HashDoS).

Где это применяется и обратное преобразование

Эта оптимизация в первую очередь защищает приложения, использующие HashMap для обработки ненадёжных входных данных (например, парсинг HTTP-заголовков, JSON от клиентов). Если из дерева удаляются элементы и его размер падает ниже другого порога (UNTREEIFY_THRESHOLD, обычно 6), оно снова преобразуется обратно в список. Это сохраняет память, так как дерево требует больше накладных расходов, чем список.

Вывод: Использование дерева в бакетах HashMap — это защитная оптимизация, которая обеспечивает предсказуемо хорошую производительность (O(log n)) даже в худшем случае множественных коллизий хэш-кодов. Это делает структуру данных более устойчивой и надёжной для использования в критически важных или публичных приложениях.