Aká je časová zložitosť získania prvku z HashMap, ak sa vo vnútri používa červená-čierna strom?

V Jave, od verzie 8, ak v bucket-e HashMap je príliš veľa kolízií (viac ako 8 prvkov), zoznam vo vnútri bucket-u sa premení na červenú-čiernu stromu na zlepšenie výkonu.

Časová zložitosť získania prvku z HashMap v tomto prípade sa mení z amortizovaného O(1) (pri použití prepojeného zoznamu) na O(log n), kde n je počet prvkov v danom bucket-e (teda hĺbka stromu).

Takže, pri použití červeno-čierneho stromu vo vnútri bucket-u, vyhľadávanie prvku sa vykonáva v O(log n).