How is collision handling implemented in a HashMap data structure?

In the HashMap data structure, collisions are handled using chaining. This means that when computing the hash code of a key and determining the index in the array, if there is already an element at that index (a collision), the new element is added to a linked list (or a tree if there are many elements) in that bucket.

Starting from Java 8, if the number of elements in a bucket exceeds a certain threshold (usually 8), the linked list is converted into a balanced tree (TreeNode), which improves search performance from O(n) to O(log n).

An example of simplified logic:

int index = hash(key) % table.length;
if (table[index] == null) {
    table[index] = new Node(key, value);
} else {
    // add to linked list or tree
    Node current = table[index];
    while (current.next != null) {
        if (current.key.equals(key)) {
            current.value = value; // update value
            return;
        }
        current = current.next;
    }
    current.next = new Node(key, value);
}

Thus, HashMap effectively handles collisions, providing quick access to elements.