Kāda ir laika sarežģītība, iegūstot elementu no HashMap, ja tās iekšpusē tiek izmantots sarkans-melns koks?

Java sākot ar versiju 8, ja HashMap grozā ir pārāk daudz kolīziju (vairāk nekā 8 elementi), groza iekšējais saraksts tiek pārveidots par sarkano-melno koku, lai uzlabotu veiktspēju.

Laika sarežģītība, iegūstot elementu no HashMap šajā gadījumā, mainās no amortizētā O(1) (lietas saistīta saraksta gadījumā) uz O(log n), kur n ir konkrētā groza elements (t.i., koka dziļums).

Tādējādi, izmantojot sarkano-melno koku grozā, elementa meklēšana notiek O(log n) laikā.