Mekkora a komplexitása egy elem keresésének kulcs szerint egy HashMap-ben?

Átlagos komplexitás O(1), a legrosszabb esetben pedig — O(n).

• Átlagos eset (O(1)): Jó hash függvény és egyenletes eloszlás esetén az elemek a kosarakban (buckets) a kulcs hash értékének kiszámításával és közvetlen hozzáféréssel a megfelelő kosárhoz, a keresés időben korlátozódik. A kosárban, ha nincsenek ütközések, az elem konstans idő alatt megtalálható.
• Legrosszabb eset (O(n)): Akkor fordul elő, amikor minden elem ugyanabba a kosárba kerül hash-elés során. Ebben az esetben a keresés lineáris kereséssé alakul egy láncolt listában (vagy egy kiegyensúlyozott fában Java 8+ esetén, ha sok elem van a kosárban, de még a fa bejárása is O(log n) lehet, ami sok ütközés esetén közelít az O(n)-hez).

Java 8-tól kezdve, azokban a kosarakban, amelyek több mint egy meghatározott küszöbértéket (TREEIFY_THRESHOLD, alapértelmezett 8) tartalmaznak, a láncolt lista egy kiegyensúlyozott fára (Piros-Fekete fa) alakul át. Ez javítja a legrosszabb esetet a keresésben egy kosáron belül O(log n)-re, de ha minden kulcs ugyanazt a hash-t kapja, akkor az általános keresés továbbra is közel lehet az O(n)-hez.