Under what conditions do operations in HashMap have a time complexity proportional to the size of the collection?

Operations in HashMap (for example, get, put) typically have an amortized time complexity of O(1). However, in some cases, the complexity can increase to O(n), where n is the size of the collection. This occurs if:

• All keys hash to the same bucket due to a poor hash function, leading to a long list or tree in one slot.
• Collisions are unevenly distributed, and the data structure within the bucket degrades.

In Java 8 and above, if a bucket contains too many elements, HashMap converts the linked list into a balanced tree (TreeNode), reducing the worst-case to O(log n), but not to O(1).

Thus, operations become proportional to the size of the collection under severe collisions and poor hash distribution.