При каком пороге (threshold) LinkedList в бакете HashMap преобразуется в TreeSet (красно-черное дерево)?

«При каком пороге (threshold) LinkedList в бакете HashMap преобразуется в TreeSet (красно-черное дерево)?» — вопрос из категории Java Core, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

В 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 для дерева

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

  1. Количество элементов в одном бакете (цепочке коллизий) достигает TREEIFY_THRESHOLD (8).
  2. Общее количество бакетов в HashMap не меньше MIN_TREEIFY_CAPACITY (64). Если размер меньше, происходит увеличение массива бакетов (resize) вместо treeify.

Почему именно 8 и 6? Пороги выбраны с гистерезисом, чтобы избежать частых преобразований туда-обратно при добавлении и удалении элементов на границе значения.