Kokia yra laiko sudėtingumas gaunant elementą iš HashMap, jei viduje naudojama raudona-juoda medis?

Java pradžioje nuo 8 versijos, jei HashMap kibire yra per daug kolizijų (daugiau nei 8 elementai), kibiro viduje esantis sąrašas paverčiamas raudonai-juodu medžiu, siekiant pagerinti našumą.

Laiko sudėtingumas, gaunant elementą iš HashMap šiuo atveju, keičiasi nuo amortizuoto O(1) (naudojant susietą sąrašą) iki O(log n), kur n yra konkretaus kibiro elementų skaičius (t.y., medžio gylis).

Todėl, naudojant raudonai-juodą medį kibiro viduje, elemento paieška vyksta per O(log n).