HashMap'da kalitga asoslangan elementni qidirish murakkabligi qanday?

O'rtacha murakkablik O(1), eng yomon holatda — O(n).

• O'rtacha holat (O(1)): Yaxshi hash funktsiyasi va elementlarning qutilarga (buckets) teng taqsimlanishi bilan, qidiruv kalitning hashini hisoblash va mos keladigan qutiga to'g'ridan-to'g'ri kirishni anglatadi. Qutida, agar kolliziyalar bo'lmasa, element konstant vaqt ichida topiladi.
• Eng yomon holat (O(n)): Barcha elementlar bir xil qutiga hashlanganida yuzaga keladi. Bu holatda, qidiruv chiziqli ro'yxat bo'yicha qidiruvga aylanadi (yoki Java 8+ da ko'p elementli qutilar uchun muvozanatli daraxtda, lekin daraxtni aylanib chiqish ham O(log n) olishi mumkin, va ko'p kolliziyalar bo'lsa, umumiy O(n) ga yaqinlashadi).

Java 8 dan boshlab, TREEIFY_THRESHOLD (standart 8) dan ortiq elementlar bilan qutilar uchun, bog'langan ro'yxat muvozanatli daraxtga (Qizil-oq daraxt) aylantiriladi. Bu, bitta qutidagi eng yomon holat qidiruvini O(log n) ga yaxshilaydi, ammo agar barcha kalitlar bir xil hashga ega bo'lsa, umumiy qidiruv hali ham O(n) ga yaqin bo'lishi mumkin.