Kokia yra elemento paieškos sudėtingumas pagal raktą HashMap'e?

Vidutinė sudėtingumas yra O(1), blogiausiu atveju — O(n).

• Vidutinis atvejis (O(1)): Su gera maišos funkcija ir vienodai paskirstytais elementais į kibirus (buckets), paieška sumažėja iki maišos skaičiavimo ir tiesioginio prieigos prie atitinkamo kibiro masyve. Kibire, jei nėra kolizijų, elementas randamas per pastovų laiką.
• Blogiausias atvejis (O(n)): Kai visi elementai yra maišomi į tą patį kibirą. Tokiu atveju paieška tampa linijiniu paieška susietame sąraše (arba subalansuotame medyje Java 8+ už daug elementų turinčius kibirus, bet net ir medžio perėjimas gali užtrukti O(log n), o jei daug kolizijų, tai artėja prie O(n)).

Nuo Java 8, jei kibiras turi daugiau nei tam tikrą slenkstį (TREEIFY_THRESHOLD, numatytas 8) elementų, susietas sąrašas paverčiamas subalansuotu medžiu (raudonai-juodu medžiu). Tai pagerina blogiausio atvejo paiešką viename kibire iki O(log n), tačiau jei visi raktai turi tą patį maišą, bendroji paieška vis dar gali būti arti O(n).