Pourquoi HashMap utilise-t-il un arbre rouge-noir au lieu d'un arbre binaire ordinaire?

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

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