Ответ
В Java 8+ HashMap для борьбы с деградацией производительности при коллизиях преобразует цепочку узлов (LinkedList) в сбалансированное дерево (TreeNode, реализация красно-черного дерева).
Ключевые константы:
static final int TREEIFY_THRESHOLD = 8; // Порог для преобразования в дерево
static final int UNTREEIFY_THRESHOLD = 6; // Порог для обратного преобразования в список
static final int MIN_TREEIFY_CAPACITY = 64; // Минимальный общий размер HashMap для дерева
Условия преобразования:
- Количество элементов в одном бакете (цепочке коллизий) достигает
TREEIFY_THRESHOLD(8). - Общее количество бакетов в
HashMapне меньшеMIN_TREEIFY_CAPACITY(64). Если размер меньше, происходит увеличение массива бакетов (resize) вместо treeify.
Почему именно 8 и 6? Пороги выбраны с гистерезисом, чтобы избежать частых преобразований туда-обратно при добавлении и удалении элементов на границе значения.