Tell me about collisions in HashMap.

A collision in HashMap occurs when two different keys have the same hash code. This does not lead to data loss but affects performance.

When inserting an element:

1. The hashCode() of the key is called.
2. The index of the bucket in the array is calculated based on the hash code.
3. If the bucket is empty, the element is inserted.
4. If the bucket already contains elements, equals() is called for each element in the bucket with the new key.
5. If equals() returns true, the value is updated.
6. If equals() always returns false, the new element is added to the bucket.

Before Android 7.0 (Nougat), HashMap used linked lists to resolve collisions. With a large number of collisions in one bucket, searching the linked list becomes O(n), where n is the number of elements in the bucket.

From Android 7.0 onwards, for buckets with many collisions (threshold of 8 elements), HashMap automatically converts the linked list into a red-black tree (TreeNode). Searching in the tree has a complexity of O(log n), significantly improving performance with many collisions. If the number of elements in the bucket drops below the threshold (threshold of 6 elements), the tree is converted back into a linked list.

A good implementation of hashCode() and equals() for custom objects is key to minimizing collisions and ensuring HashMap efficiency.

Example:

@Override
public int hashCode() {
    // Example of a good hashCode implementation
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Example of a correct equals implementation
    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);
}