What is the time complexity of inserting a new element into a HashMap data structure?

The average time complexity of inserting a new element into a HashMap is O(1). This is achieved through the use of a hash function that computes the index of the bucket for storing the element.

However, in the worst case, when there are many collisions and elements end up in the same bucket, the complexity can degrade to O(n), where n is the number of elements in the HashMap.

Modern implementations of Java HashMap (starting from Java 8) convert linked lists into balanced trees when there are many collisions, which improves the worst-case scenario to O(log n).

Thus, insertion is usually very fast and efficient, but depends on the quality of the hash function and key distribution.