How is the insertion operation's time complexity in HashMap determined?

The average time complexity of inserting an element into a HashMap in Java is O(1) — constant time. This is achieved by using a hash function for quick position determination.

However, in the worst case, if a collision occurs and all elements end up in one bucket, the insertion can degrade to O(n), where n is the number of elements in that bucket.

Starting from Java 8, when there are many collisions, the bucket is converted from a linked list to a balanced tree (TreeMap), which improves the worst case to O(log n).

Example:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42); // insertion in average O(1)