Ինչպես է որոշվում մուտքի ժամանակը HashMap տվյալների կառուցվածքում?

Java-յի HashMap տվյալների կառուցվածքում տարրին մուտքի ժամանակը սովորաբար համարվում է հաստատուն — O(1): Դա հասնում է հեշ-ֆունկցիայի օգտագործմամբ, որը փոխում է բանալիին զանգվածի ինդեքս, որտեղ պահվում է արժեքը:

Սակայն պրակտիկայում մուտքի ժամանակը կարող է աճել մինչև O(n) ամենավատ դեպքերում, եթե շատ կոլիզիաներ (տարբեր բանալիներ նույն հեշով) տեղի ունենան, և տարրերը պահվում են միացված ցանկում կամ ծառի ներսում մեկ բջիջում:

Java 8-ից սկսած, կոլիզիաների դեպքում մուտքի ժամանակը նվազեցնելու համար, կապված ցանկը փոխարկվում է հավասարակշռված ծառի (TreeMap), ինչը նվազեցնում է որոնման ժամանակը այդ դեպքերում մինչև O(log n):

Այսպիսով, միջին մուտքի ժամանակը մոտ է O(1)-ի, բայց ամենավատ դեպքերում կարող է լինել O(log n) կամ O(n):