Каква е сложността на търсенето на елемент по ключ в HashMap?

Средната сложност е O(1), в най-лошия случай — O(n).

• Среден случай (O(1)): При добра хеш функция и равномерно разпределение на елементите по кошовете, търсенето се свежда до изчисляване на хеша на ключа и директен достъп до съответния кош в масива. Вътре в коша, ако няма колизии, елементът се намира за константно време.
• Най-лош случай (O(n)): Настъпва, когато всички елементи са хеширани в един и същи кош. В такъв случай търсенето става линейно търсене в свързан списък (или в балансирано дърво в Java 8+ за кошове с много елементи, но дори преминаването през дървото може да отнеме O(log n), което при много колизии в един кош все още се приближава до O(n)).

От Java 8 нататък, за кошове, съдържащи повече от определен праг (TREEIFY_THRESHOLD, по подразбиране 8) елемента, свързаният списък се преобразува в балансирано дърво (червено-черно дърво). Това подобрява най-лошия случай на търсене в рамките на един кош до O(log n), но ако всички ключове имат еднакъв хеш, общото търсене все още може да бъде близо до O(n).