How is a collision of keys handled when using Bucket in a HashMap?

In Java, HashMap uses a data structure called a bucket to handle collisions, which initially is a linked list of elements with the same hash.

When two keys have the same hash (collision), both are placed in the same bucket. During search or insertion, the elements of this bucket are traversed to compare keys using the equals() method.

Starting from Java 8, if the number of elements in a bucket exceeds a certain threshold (usually 8), the linked list is transformed into a balanced tree (TreeMap) to speed up search from O(n) to O(log n).

Example:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2); // if key1 and key2 have the same hash, they will be in the same bucket
Integer value = map.get("key1"); // traversing bucket elements to find the key