HashMap'dagi to'qnashuvlar haqida gapiring.

HashMapda to‘qnashuv, ikki xil kalitning bir xil hash-kodga ega bo‘lganda yuzaga keladi. Bu ma'lumotlarni yo‘qotishga olib kelmaydi, lekin ishlash tezligini pasaytiradi.

Element qo‘shishda:

1. Kalitning hashCode() metodi chaqiriladi.
2. Hash-kod asosida arraydagi bucket indeks hisoblanadi.
3. Agar bucket bo‘sh bo‘lsa, element joylashtiriladi.
4. Agar bucketda allaqachon elementlar bo‘lsa, har bir element uchun equals() chaqiriladi va yangi kalit bilan solishtiriladi.
5. Agar equals() true qaytarsa, qiymat yangilanadi.
6. Agar equals() doimo false qaytarsa, yangi element bucketga qo‘shiladi.

Android 7.0 (Nougat)gacha, HashMap koliziyalarni hal qilish uchun bog‘langan ro‘yxatlarni ishlatardi. Ko‘p koliziyalar bo‘lsa, ro‘yxat ichida qidiruv O(n) bo‘lib, n — bucketdagi elementlar soni.

Android 7.0 va undan keyin, ko‘p koliziyalar (8 ta elementgacha) bo‘lsa, HashMap avtomatik ravishda bog‘langan ro‘yxatni qizil-siyoh daraxtiga (TreeNode) aylantiradi. Daraxtda qidiruv O(log n) bo‘lib, katta koliziyalar uchun ishlash samaradorligini sezilarli darajada oshiradi. Agar bucketdagi elementlar soni yana pastga tushib, 6 ta elementdan kam bo‘lsa, daraxt yana bog‘langan ro‘yxatga aylantiriladi.

Foydalanuvchi tomonidan yaratilgan obyektlar uchun hashCode() va equals() metodlarining yaxshi ishlashini ta'minlash koliziyalarni minimallashtirish va HashMap samaradorligini oshirish uchun muhimdir.

Misol:

@Override
public int hashCode() {
    // Yaxshi hashCode metodining misoli
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // To‘g‘ri equals metodining misoli
    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);
}