Вопрос проверяет знание оптимизаций HashMap, появившихся в Java 8, и понимание защиты от худших сценариев.
Начиная с Java 8, бакет HashMap может превращаться в красно-чёрное дерево.
Это происходит при большом количестве элементов в одном бакете.
Цель — ограничить деградацию операций до O(log n).
Дерево используется не всегда, а только при выполнении ряда условий.
Это улучшает стабильность производительности.
Деревья в HashMap — это механизм защиты от чрезмерных коллизий.
Бакет превращается в дерево, если:
количество элементов в бакете ≥ 8
общий размер HashMap ≥ 64
Причина второго условия:
при маленьком размере выгоднее расширить таблицу
а не усложнять структуру бакета
Для корректной работы дерева:
ключи должны реализовывать Comparable
либо быть сравнимыми между собой
Если это невозможно:
используется fallback-механизм сравнения
но дерево всё равно создаётся
список заменяется на красно-чёрное дерево
поиск становится O(log n)
операции стабилизируются даже при атаках на hashCode()
Если размер бакета уменьшается:
при количестве элементов ≤ 6
дерево снова превращается в список
Treeify — это оптимизация, которая делает HashMap устойчивой к худшим сценариям и атакам на хеширование.
