Использование сбалансированного дерева вместо связанного списка является компромиссом.В случае списка необходимо выполнить линейное сканирование, чтобы выполнить поиск в сегменте, в то время как дерево допускает доступ во время регистрации.Когда список небольшой, поиск выполняется быстро, и использование дерева на самом деле не дает выгоды, в то время как около 8 или около того элементов стоимость поиска в списке становится достаточно значительной, чтобы дерево обеспечивало ускорение.
Я подозреваю, что использование дерева предназначено для исключительного случая, когда хеш ключа катастрофически нарушается (например, сталкиваются многие ключи);в то время как линейный поиск приведет к значительному снижению производительности, использование дерева несколько снижает эту потерю производительности, , если ключи напрямую сопоставимы.
Поэтому точный порог из 8 записей может небыть ужасно значимым: вероятность того, что корзина дерева равна 0,00000006, при условии хорошего распределения ключей, поэтому корзины с деревом, очевидно, используются очень редко в таком случае.Когда алгоритм хеширования терпит неудачу катастрофически, тогда число ключей в корзине в любом случае намного больше 8.
Это приводит к пробелу в пространстве, так как узел дерева должен включать дополнительные ссылки: четыре ссылки на узлы дереваи логическое в дополнение к полям LinkedHashMap.Entry (см. его источник ).
Из комментариев в источнике класса HashMap :
Поскольку узлы TreeNode примерно в два раза больше обычных узлов, мы используем их только тогда, когда ячейки содержат достаточно узлов, чтобы гарантировать их использование (см. TREEIFY_THRESHOLD).А когда они становятся слишком маленькими (из-за удаления или изменения размера), они превращаются обратно в обычные контейнеры.При использовании хорошо распределенных пользовательских хеш-кодов редко используются бункеры деревьев.В идеале при случайных хэш-кодах частота узлов в ячейках следует распределению Пуассона (http://en.wikipedia.org/wiki/Poisson_distribution) с параметром в среднем около 0,5 для порога изменения размера по умолчанию 0,75, хотя и с большой дисперсией из-за изменения размера гранулярности.дисперсия, ожидаемые появления размера списка k: (exp (-0.5) * pow (0.5, k) / factorial (k)).