Вопрос проверяет знание внутренних оптимизаций HashMap и отличий между версиями Java.
При одинаковом hashCode() все элементы окажутся в одном bucket’е. Изначально они будут храниться в виде связанного списка. Начиная с Java 8, при превышении определенного порога список может быть преобразован в дерево. Это улучшает производительность поиска. Однако сам HashMap не превращается полностью в список или дерево.
Важно различать структуру всего HashMap и структуру внутри одного bucket’а.
В версиях Java до 8:
каждый bucket представлял собой связанный список
при большом количестве коллизий операции становились O(n)
Это делало HashMap уязвимым к деградации производительности.
Начиная с Java 8:
при превышении порога элементов в bucket’е
связанный список преобразуется в красно-черное дерево
Это позволяет:
снизить сложность поиска до O(log n)
уменьшить влияние плохого hashCode()
Дерево создается только если:
количество элементов превышает порог
размер таблицы достаточный
ключи поддерживают сравнение
В противном случае остается список.
HashMap по-прежнему состоит из массива bucket’ов
только один bucket может стать деревом
остальные bucket’ы остаются пустыми
Вывод: при плохом hashCode() деградация смягчается деревьями, но проблема равномерного распределения остается.
