Ի՞նչ է HashMap-ի տարրերի վրա գործողությունների ժամանակային բարդությունը, և արդյոք HashMap-ը երաշխավորում է նշված բարդությունը տարր ընտրելիս:

HashMap հիմնական գործողությունների (get, put, remove, containsKey) ժամանակային բարդությունը միջինում կազմում է O(1):

Սա հասնում է հեշ-թերթի օգտագործմամբ, որտեղ տարրերը պահվում են բջիջներում (կաթոցներում), որոնք որոշվում են բանալիի հեշ-կոդով: Իդեալ դեպքում, յուրաքանչյուր կաթոցում միայն մեկ տարր է:

Սակայն, ամենավատ դեպքում, երբ բոլոր բանալիները ունեն նույն հեշ-կոդը կամ տեղի են ունենում շատ բախումներ, տարրերը հայտնվում են նույն կաթոցում: Այդ դեպքում, կաթոցը կարող է վերածվել կապված ցանկի (Java 8-գա) կամ ծառի (Java 8 և բարձր, եթե կաթոցում տարրերի թիվը գերազանցում է որոշակի շեմը): Այսպիսի կաթոցում գործողությունները ունեն ժամանակային բարդություն O(n), որտեղ n - այդ կաթոցում տարրերի թիվն է:

HashMap չի երաշխավորում կայուն ժամանակային բարդություն O(1) տարրին հասնելու համար: Գերազանցապես, այն երաշխավորում է միջին O(1): Ամենավատ դեպքում, բարդությունը կարող է լինել O(n):

Ժամանակային բարդությանը ազդող գործոններ:

• Հեշ-ֆունկցիայի որակը: Լավ հեշ-ֆունկցիան հավասարապես տարածում է բանալիները, նվազեցնելով բախումները:

• load factor (բեռի գործակից): Կարգավորում է, թե որքանով կարող է լցված լինել հեշ-թերթը, նախքան նրա չափը մեծացնելը (rehash): Բարձր load factor-ը կարող է մեծացնել բախումների հավանականությունը:

• Սկզբնական ծավալը: Շատ փոքր սկիզբնական ծավալը մեծ քանակությամբ տարրերով հաճախ rehash-ների պատճառ է դառնում, ինչը ռեսուրսների մեծ պահանջ է: