Ispričajte o kolizijama u 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);
}