Perché HashMap utilizza un albero rosso-nero invece di un normale albero binario?

В Java HashMap для хранения элементов в одной корзине (bucket) при коллизиях используется красно-черное дерево вместо обычного бинарного дерева, чтобы гарантировать сбалансированность и, следовательно, логарифмическое время поиска, вставки и удаления.

Обычное бинарное дерево может деградировать до линейной структуры (списка) при неблагоприятном порядке вставки, что ухудшает производительность до O(n). Красно-черное дерево — самобалансирующееся, что обеспечивает стабильную производительность даже при большом количестве коллизий.