Превратится ли HashMap в связанный список или дерево, если hashCode() у ключей всегда возвращает одно и то же значение?

Question

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

YeaHub · Accepted Answer

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