Jaka jest złożoność czasowa pobierania elementu z HashMap, jeśli wewnątrz używany jest czerwono-czarny drzewo?

W Java, od wersji 8, jeśli w kubełku HashMap jest zbyt wiele kolizji (więcej niż 8 elementów), lista wewnątrz kubełka jest przekształcana w drzewo czerwono-czarne w celu poprawy wydajności.

Złożoność czasowa uzyskania elementu z HashMap w tym przypadku zmienia się z amortyzowanego O(1) (przy użyciu listy powiązanej) na O(log n), gdzie n to liczba elementów w danym kubełku (czyli głębokość drzewa).

W związku z tym, przy użyciu drzewa czerwono-czarnego w kubełku, wyszukiwanie elementu odbywa się w czasie O(log n).