Каква е времевата сложност при получаване на елемент от HashMap, ако вътре се използва червено-черно дърво?

В Java, от версия 8 насам, ако в кошче на HashMap има твърде много сблъсъци (повече от 8 елемента), списъкът вътре в кошчето се преобразува в червено-черно дърво за подобряване на производителността.

Времевата сложност за получаване на елемент от HashMap в този случай се променя от амортизираното O(1) (при използване на свързан списък) на O(log n), където n е броят на елементите в конкретното кошче (т.е. дълбочината на дървото).

Така, при използване на червено-черно дърво вътре в кошчето, търсенето на елемент се извършва за O(log n).