Ինչպե՞ս է գնահատվում HashMap-ում բանալիով տարր որոնելու արդյունավետությունը բախումների դեպքում։

Նույն HashMap-ում, տարր որոնումը բանալիով միջինում տեղի է ունենում ժամանակով O(1), բայց կոլիզիաների դեպքում արդյունավետությունը կախված է դրանց մշակման մեթոդից:

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

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

Արդյունքում՝

• Փոքր կոլիզիաներով որոնումը մնում է մոտ O(1):
• Մեծ կոլիզիաներով մեկ զամբյուղում որոնումը կլինի O(log n):

Այս բարելավումը զգալիորեն բարձրացնում է HashMap-ի կատարողականությունը անբարենպաստ սցենարներում։