Explain what a key collision means in a HashMap data structure and how it handles it.

Hash collision in HashMap occurs when two different keys produce the same hash value for storage in the array.

How HashMap handles this:

• In Java, HashMap uses linked lists or balanced trees to store multiple elements that fall into the same bucket.
• When adding a new element with a key whose hash matches an existing one, the new element is added to the chain of that bucket.
• When searching for a key, HashMap iterates through the chain, comparing keys using the equals() method to find the correct one.

Starting from Java 8, if the chain becomes too long, it is converted into a balanced tree (TreeNode), which improves search performance from O(n) to O(log n).