Պատմեք HashMap- ի բախումների մասին։

HashMap-ում բախում առաջանում է, երբ երկու տարբեր բանալիներ ունեն նույն hash-կոդը: Սա չի հանգեցնում տվյալների կորուստի, բայց ազդում է արդյունավետության վրա:

Ամեն անգամ, երբ ավելացվում է տարր՝

1. Կոչվում է hashCode()-ը բանալիի համար:
2. Հաշվարկվում է բաքի ինդեքսը hash-կոդի հիման վրա:
3. Եթե բաքը դատարկ է, տարրն ավելացվում է:
4. Եթե բաքը արդեն պարունակում է տարրեր, equals()-ը կանչվում է յուրաքանչյուր տարրի համար նոր բանալիով:
5. Եթե equals()-ը վերադարձնում է true, արժեքը թարմացվում է:
6. Եթե equals()-ը միշտ false է վերադարձնում, նոր տարրն ավելացվում է բաքին:

Նախքան Android 7.0 (Nougat), HashMap-ը օգտագործում էր կապված ցանկեր՝ բախումները լուծելու համար: Երբ բաքում շատ բախումներ լինեն, որոնումը կապված ցանկում դառնում է O(n), որտեղ n — բաքում գտնվող տարրերի քանակը:

Android 7.0-ից հետո, մեծ բախումներ ունեցող բաքերի համար (սահմանաչափ 8 տարր), HashMap-ը ավտոմատ կերպով փոխում է կապված ցանկը կարմիր-սև ծառի (TreeNode)։ Ծառի որոնումը ունի բարդություն O(log n), ինչը զգալիորեն բարելավում է արդյունավետությունը մեծ բախումների դեպքում։ Եթե բաքում տարրերի քանակը կրկին նվազի սահմանաչափից (6 տարր), ծառը վերածվում է կրկին կապված ցանկի:

Լավ hashCode() և equals() իրականացման օրինակ՝ օգտագործվող օբյեկտների համար, կարևոր է բախումների նվազեցման և HashMap-ի արդյունավետության ապահովման համար:

Օրինակ՝

@Override
public int hashCode() {
    // Լավ hashCode իրականացման օրինակ
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Ճիշտ `equals()` իրականացման օրինակ
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    MyObject myObject = (MyObject) o;
    return field2 == myObject.field2 &&
           field1.equals(myObject.field1);
}