HashMapтеги кагылыштар жөнүндө айтып бериңиз.

HashMap-де қақтығыс екі түрлі кілттің бірдей хеш-кодқа ие болғанда пайда болады. Бұл деректердің жоғалуына әкелмейді, бірақ өнімділікке әсер етеді.

Элементті қосу кезінде:

1. Кілттің hashCode() әдісі шақырылады.
2. Хеш-код негізінде массивтегі бакеттің индексі есептеледі.
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);
}