При каких условиях бакет HashMap превращается в красно-чёрное дерево?

Question

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

YeaHub · Accepted Answer

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