How is the execution time determined when there are collisions in HashMap?

In Java, HashMap operation times (e.g., get, put) are on average O(1) thanks to key hashing. However, in case of collisions (when different keys have the same hash), elements are stored in a single bucket.

Previously in Java (before version 8), in case of collisions, elements in the bucket were stored as a linked list, which worsened access time to O(n) in the worst case if all elements ended up in one bucket.

Starting from Java 8, when a certain threshold of elements in a bucket is reached (usually 8), the linked list is transformed into a balanced tree (e.g., red-black tree). This improves access time to O(log n) in the worst case.

Thus, in the presence of collisions, HashMap operation times change:

• Few collisions — time close to O(1)
• Many collisions — time can degrade to O(log n) thanks to the tree

Example:

Map<String, String> map = new HashMap<>();
map.put("key1", "value1");
map.put("key2", "value2");
String val = map.get("key1");

If "key1" and "key2" have the same hash, they will fall into the same bucket, and the search will proceed through the structure inside the bucket.