HashMap-də açar ilə element axtarışının mürəkkəbliyi nədir?

Orta hesablaşıb O(1)-dir, ən pis vəziyyətdə isə — O(n).

• Orta vəziyyət (O(1)): Yaxşı hash funksiyası və elementlərin qutulara (buckets) bərabər paylanması ilə axtarış, açarın hash kodunun hesablanması və müvafiq qutunun birbaşa əldə olunması ilə məhdudlaşır. Qutunun içində, əgər kolliziyalar yoxdursa, element sabit vaxtda tapılır.
• Ən pis vəziyyət (O(n)): Bütün elementlərin eyni qutuda hash-lənməsi halında baş verir. Bu halda, axtarış əlaqəli siyahıda lineyar axtarışa çevrilir (və ya Java 8+ üçün çox sayda element olan qutular üçün balanslı ağacda, lakin ağacı keçmək də O(log n) vaxt ala bilər, və çox kolliziyalar olarsa, ümumi O(n)-ə yaxınlaşır).

Java 8-dən başlayaraq, TREEIFY_THRESHOLD (standart 8) dəyərindən çox element olan qutular üçün, əlaqəli siyahı balanslı ağaca (Qırmızı-qaranlıq ağac) çevrilir. Bu, tək bir qutunun içindəki ən pis axtarış vəziyyətini O(log n)-ə yaxşılaşdırır, lakin bütün açarların eyni hash-ə malik olması halında, ümumi axtarış hələ də O(n)-ə yaxın ola bilər.