What is the time complexity of inserting an element into a HashMap in the worst-case scenario?

The average time complexity of inserting an element into a HashMap in Java is O(1), but in the worst case, it can reach O(n).

The worst case occurs when all keys hash to the same bucket, meaning they have the same hash code or collisions are poorly distributed. In this case, HashMap behaves like a linked list (or a balanced tree from Java 8 onwards), and insertion requires traversing the elements in that bucket.

Since Java 8, if the number of elements in a bucket exceeds a certain threshold, the structure changes from a list to a red-black tree, improving the worst-case to O(log n).

In summary:

• Average case: O(1)
• Worst case before Java 8: O(n)
• Worst case with Java 8 and above: O(log n)