Что происходит при превышении 7 элементов в одном бакете HashMap в Java

Что проверяют

Знаете ли вы, как HashMap ведёт себя при плохом распределении хешей, и понимаете ли, зачем понадобилось дерево. Вопрос на чтение исходников, но с практическим хвостом про качество hashCode и про устойчивость к специально подобранным ключам.

Как отвечать

С Java 8 бакет это не только связный список. Когда цепочка в одном бакете дорастает до порога TREEIFY_THRESHOLD, равного восьми, список превращается в красно-чёрное дерево, и поиск внутри бакета становится логарифмическим вместо линейного.

Дальше оговорка, ради которой вопрос и задают: превращения не будет, пока длина массива бакетов меньше MIN_TREEIFY_CAPACITY, то есть шестидесяти четырёх. В маленькой таблице длинная цепочка означает не плохой хеш, а тесноту, поэтому вместо дерева выполняется resize. Обратный переход тоже есть: при перестройке таблицы дерево, в котором осталось не больше шести узлов (UNTREEIFY_THRESHOLD), разворачивается обратно в список.

Стоит сказать, что дерево упорядочивает узлы по хешу, а при совпадении использует Comparable, если ключ его реализует, иначе работает запасное правило сравнения и выигрыш скромнее. И что узел дерева занимает заметно больше памяти, чем узел списка, поэтому механизм задуман как страховка от вырождения, а не как обычный режим.

Где спотыкаются

Говорят, что дерево появляется сразу по достижении восьми элементов в бакете. Пока массив короче шестидесяти четырёх, вызов уйдёт в расширение таблицы, и на маленькой карте дерева не увидеть, сколько коллизий ни создавай.

Второе: путают пороги с числом записей. Шестьдесят четыре это длина массива бакетов, а не размер карты, восемь это длина цепочки в одном бакете, а не общее количество элементов. От перестановки этих чисел ответ разваливается на уточняющем вопросе.

Третье: считают дерево лекарством от плохого hashCode. Если ключи дают один и тот же хеш и не сравнимы между собой, логарифма не получится. Лечит нормальный hashCode и неизменяемый ключ: объект, у которого хеш меняется после вставки, теряется в карте независимо от того, список в бакете или дерево.