Какова роль константы TREEIFY_THRESHOLD в HashMap?

TREEIFY_THRESHOLD — это константа в классе java.util.HashMap, определяющая пороговое значение (по умолчанию 8). Когда количество элементов в одной корзине (бакете) хэш-таблицы достигает этого значения, структура данных в этой корзине преобразуется из односвязного списка в красно-чёрное дерево.

Цель: Оптимизация производительности в случае большого количества коллизий хэш-кодов.

• Список: Поиск в худшем случае имеет сложность O(n).
• Дерево: Поиск в худшем случае имеет сложность O(log n), что значительно быстрее при n >= 8.

Пример сценария:

import java.util.HashMap;
import java.util.Map;

public class TreeifyExample {
    public static void main(String[] args) {
        Map<Key, Integer> map = new HashMap<>();
        // Класс Key с переопределённым hashCode(), всегда возвращающим 1 (идеальная коллизия)
        for (int i = 0; i < 10; i++) {
            map.put(new Key(i), i);
            // После добавления 8-го элемента в одну корзину,
            // список в ней преобразуется в красно-чёрное дерево.
        }
        System.out.println("Map size: " + map.size());
    }

    static class Key {
        int id;
        Key(int id) { this.id = id; }
        @Override
        public int hashCode() { return 1; } // Намеренная коллизия
    }
}

Связанные константы:

• UNTREEIFY_THRESHOLD (по умолчанию 6): Если количество элементов в корзине-дереве уменьшается до этого значения при удалении или изменении размера таблицы, дерево преобразуется обратно в список для экономии памяти.
• MIN_TREEIFY_CAPACITY (по умолчанию 64): Минимальная общая вместимость (capacity) хэш-таблицы, при которой возможно преобразование списка в дерево. Если корзина переполнена, но общий размер таблицы мал, она будет просто увеличена (resized).

Важно: Преобразование происходит только если ключи реализуют интерфейс Comparable, иначе дерево не может быть эффективно построено.