Какие структуры используются внутри бакета в современных версиях Java?

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

Гибридный подход: список и дерево

Современная реализация использует адаптивную структуру:

• Односвязный список: используется по умолчанию при добавлении элементов в бакет. Это эффективно для небольшого числа коллизий.
• Красно-чёрное дерево: когда количество узлов в бакете превышает константу TREEIFY_THRESHOLD (значение 8) и общий размер таблицы (массива бакетов) не меньше MIN_TREEIFY_CAPACITY (значение 64), список преобразуется в сбалансированное красно-чёрное дерево. Это гарантирует время поиска O(log n) даже при многих коллизиях.

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

Рассмотрим ключевые константы и логику преобразования:

// Упрощённая логика из исходного кода HashMap
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

// При добавлении элемента в бакет:
if (binCount >= TREEIFY_THRESHOLD - 1) {
    if (tab.length >= MIN_TREEIFY_CAPACITY) {
        treeifyBin(tab, hash); // Преобразует список в дерево
    } else {
        resize(); // Увеличивает размер таблицы вместо дерева
    }
}

Обратное преобразование дерева обратно в список происходит, когда количество элементов в бакете падает ниже UNTREEIFY_THRESHOLD (значение 6). Это гистерезис предотвращает частые преобразования при колебаниях размера.

Где это применяется и зачем нужно

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

Вывод: Гибридная структура бакета (список/дерево) в Java HashMap — это оптимизация для защиты от худшего случая. Она обеспечивает высокую скорость при обычном использовании (список) и сохраняет логарифмическую сложность при большом числе коллизий (дерево), что делает структуру надёжной для production-систем.