How does a red-black tree work in HashMap?

In Java, from Java 8 onwards, HashMap uses a Red-Black Tree to optimize performance when there are many collisions. Initially, when collisions occur, elements in a bucket are stored as a linked list. If the number of elements in a bucket exceeds a threshold (usually 8), the linked list is transformed into a Red-Black Tree.

A Red-Black Tree is a balanced binary search tree that provides insertion, deletion, and search operations in O(log n) time in the worst case. This significantly improves performance compared to linear search in a list.

Thus, when there are many collisions, HashMap switches from a list to a Red-Black Tree for a specific bucket, allowing faster find, insert, and delete operations in that bucket.

An example of simplified transformation logic:

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

Where treeifyBucket transforms the linked list into a Red-Black Tree.