Koja je vremenska složenost dobijanja elementa iz HashMap-a ako se unutar koristi crveno-crno drvo?

U Javi, od verzije 8, ako u bucket-u HashMap postoji previše kolizija (više od 8 elemenata), lista unutar bucket-a se pretvara u crveno-crni stablo radi poboljšanja performansi.

Vremenska složenost za dobijanje elementa iz HashMap u ovom slučaju menja se sa amortizovanog O(1) (kada se koristi povezani spisak) na O(log n), gde je n broj elemenata u tom bucket-u (tj. dubina stabla).

Tako, korišćenjem crveno-crnog stabla unutar bucket-a, pretraživanje elementa se obavlja u O(log n).