Что происходит с бакетом при переполнении в HashMap

При переполнении бакета в HashMap происходит преобразование связного списка в красно-черное дерево (если ключи реализуют Comparable), начиная с Java 8. Это улучшает производительность с O(n) до O(log n) при коллизиях.

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

1. Размер бакета превышает TREEIFY_THRESHOLD (8 элементов).
2. Общий размер HashMap превышает MIN_TREEIFY_CAPACITY (64).

Если условия не выполнены, HashMap просто увеличивает размер массива бакетов (рехеширование).

Пример:

HashMap<Key, String> map = new HashMap<>();
// Добавляем 9 элементов с одинаковым хэшем
for (int i = 0; i < 9; i++) {
    map.put(new Key(i), "Value" + i); // Key имеет переопределенный hashCode()
}
// При 9-м элементе список превращается в дерево

Обратное преобразование (дерево → список) происходит при уменьшении элементов в бакете до UNTREEIFY_THRESHOLD (6).