Ответ
В 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? Пороги выбраны с гистерезисом, чтобы избежать частых преобразований туда-обратно при добавлении и удалении элементов на границе значения.
Ответ 18+ 🔞
Давай разжую эту тему, как будто я тебе в баре объясняю после третьего пива. Сиди, слушай.
Вот смотри, есть у нас HashMap — такая шустрая мапа, которая обычно хранит данные в массиве корзинок (бакетов). Когда у двух ключей хеш совпадает (коллизия), они просто цепляются друг за дружку в связный список внутри этой корзинки. Всё просто, всё быстро, пока список маленький.
Но представь, что какой-то упоротый разработчик или злобный пользователь подобрал ключи так, что они все летят в одну и ту же корзинку. Список становится длинным, как очередь за последним айфоном. И поиск по нему превращается в ад — нужно пройтись по всем элементам, это уже не O(1), а O(n). Производительность летит в пизду, как пуля.
Так вот, умные дядьки из Oracle на это посмотрели и сказали: «Так, блядь, не пойдёт». Начиная с Java 8, они придумали хитрожопый трюк. Когда в одной корзинке набирается дохуя элементов (а именно 8, константа TREEIFY_THRESHOLD), они не просто так оставляют этот длинный список. Нет! Они берут и превращают этот список в сбалансированное дерево (красно-чёрное, если быть точным, TreeNode).
static final int TREEIFY_THRESHOLD = 8; // Щас тебя, сука, деревом сделаем
static final int UNTREEIFY_THRESHOLD = 6; // Охлаждай пыл, обратно в список
static final int MIN_TREEIFY_CAPACITY = 64; // Маловата карта для таких амбицийНо не всё так просто, ёпта! Чтобы это деревовошление случилось, нужно соблюсти два условия, как в хорошем анекдоте:
- Кол-во в корзинке >= 8. Это понятно, порог пересилен.
- Общий размер массива корзинок в
HashMap>= 64 (MIN_TREEIFY_CAPACITY). А вот это интересно! Если карта сама по себе маленькая (меньше 64 бакетов), то вместо того чтобы городить дерево, она скажет: «Да похуй», — и просто увеличит размер всего массива бакетов (resize). Часто после этого элементы перераспределятся, и длинные списки сами рассосутся. Экономия на спичках, блядь.
А теперь самый сок — почему 8 и 6? Почему не 10 и 8? Всё просто, это гистерезис, чувак. Чтобы не было такого, что ты добавил 9-й элемент — бац, дерево. Удалил один (стало 8) — бац, обратно в список. Добавил опять — опять дерево. Представь, на границе значения идёт добавление-удаление. Карта будет тратить всю свою энергию на эти преобразования туда-сюда, а не на работу. Это как мартышлюшка, которая не может решить, выйти на улицу или нет. Порог обратного преобразования (UNTREEIFY_THRESHOLD) сделан меньше (6), чтобы между 6 и 8 была буферная зона, где уже не дергается. Гениально и просто, как тапок.
Короче, смысл в том, чтобы предотвратить пиздец (O(n) поиск) в случае засилья коллизий, но не делать это слишком часто и дорого. Всё для твоего блага, разработчик, ебать твою душу.