Что происходит с внутренней структурой бакета в хэшмапе при большом количестве коллизий

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

Знаете ли внутренности HashMap начиная с восьмой версии и помните ли, что порог превращения в дерево не один, а два. Вопрос на глубину, его задают следом за общим «как устроена HashMap».

Как отвечать

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

Дальше самое важное. Когда в одном бакете набирается восемь узлов, список превращается в красно-чёрное дерево, но только если длина таблицы не меньше 64. Если таблица меньше, вместо дерева происходит расширение: на тесной таблице длинные цепочки обычно объясняются нехваткой бакетов, а не плохой хэш-функцией. При очередном расширении дерево, в котором осталось шесть узлов или меньше, разворачивается обратно в список. Пороги разные нарочно, чтобы структура не переключалась туда-обратно на каждой вставке.

Внутри дерева порядок задан хэшем, при равных хэшах сравниваются сами ключи, если они реализуют Comparable, иначе применяется запасной порядок.

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

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

Называют порог восемь и на этом останавливаются. Без второго условия ответ неверный: на маленькой таблице девятый элемент в бакете приведёт к расширению, а никакого дерева не появится.

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

Третье: считают, что дерево спасает от плохой хэш-функции. Оно лечит последствия, а не причину: память на узлы дерева больше, вставка дороже, и если все ключи дают один индекс, карта превращается в одно дерево и перестаёт быть картой по скорости.