Junior — Middle
Ներկայացրեք, թե ինչ է նշանակում բանալիի բախումը HashMap տվյալների կառուցվածքում և ինչպես է այն դրանով վարվում։
sobes.tech AI
Պատասխան AI-ից
HashMap- ում բանալիների բախում (hash collision) տեղի է ունենում, երբ երկու տարբեր բանալիներ հաշվարկման ժամանակ նույն ինդեքսային արժեքը են տալիս հիշողության մեջ։
Ինչպես է դա կառավարում HashMap-ը՝
- Java-ում HashMap-ը օգտագործում է շղթաներ (կապակցված ցանկեր կամ հավասարակշռված ծառեր)՝ մի քանի տարրեր պահելու համար, որոնք ընկնում են նույն բաքում։
- Նոր տարր ավելացնելիս, որի հեշը համընկնում է արդեն գոյություն ունեցողի հետ, նոր տարրն ավելացվում է այդ բաքի շղթային։
- Բանալի որոնման ժամանակ, HashMap-ը անցնում է շղթայի տարրերով և համեմատում է բանալիները equals() մեթոդով՝ ճիշտը գտնելու համար։
Java 8-ից սկսած, եթե շղթան շատ երկար է դառնում, այն փոխարկվում է հավասարակշռված ծառի (TreeNode)՝ որոնման արդյունավետությունը բարելավելու համար՝ O(n)-ից հասնելով O(log n)-ի։