Kāda ir laika sarežģītība elementa meklēšanas operācijai HashMap vidējā gadījumā?

Vidējā gadījumā, Java HashMap elementa meklēšanas operācija ir ar laika sarežģītību O(1) — konstants laiks.

Tas tiek panākts, izmantojot hašfunkciju, kas aprēķina groza (bucket) indeksu, glabājot pāri atslēga-vērtība. Ar ideālu sadalījumu starp groziem, meklēšana notiek tieši.

Tomēr sliktākajā gadījumā (piemēram, ar daudzām kolīzijām), sarežģītība var samazināties līdz O(n), kur n ir HashMap elementu skaits, ja visi elementi nokļūst vienā grozā. Modernās Java implementācijas (no Java 8) izmanto līdzsvarotus kokus (TreeNodes) grozos, ja kolīziju ir daudz, kas samazina sliktāko gadījumu līdz O(log n).

Tādēļ, lielākajā daļā praktisko gadījumu, var uzskatīt, ka meklēšana HashMap ir ar amortizētu sarežģītību O(1).