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)-ի։