Как работает красно-чёрное дерево в HashMap?

В Java HashMap с версии Java 8 для оптимизации производительности при большом количестве коллизий используется красно-чёрное дерево (Red-Black Tree). Изначально, при коллизиях, элементы в одном бакете хранятся в виде связного списка. Если количество элементов в бакете превышает порог (обычно 8), связный список преобразуется в красно-чёрное дерево.

Красно-чёрное дерево — это сбалансированное бинарное дерево поиска, которое обеспечивает операции вставки, удаления и поиска за O(log n) в худшем случае. Это значительно улучшает производительность по сравнению с линейным поиском в списке.

Таким образом, при большом числе коллизий HashMap переключается с списка на красно-чёрное дерево для конкретного бакета, что позволяет быстрее находить, вставлять и удалять элементы в этом бакете.

Пример упрощённой логики преобразования:

if (bucket.size() > TREEIFY_THRESHOLD) {
    treeifyBucket(bucket);
}

Где treeifyBucket преобразует связный список в красно-чёрное дерево.