При каких условиях операции в HashMap имеют временную сложность, пропорциональную размеру коллекции?

Операции в HashMap (например, get, put) обычно имеют амортизированную временную сложность O(1). Однако в некоторых случаях сложность может вырасти до O(n), где n — размер коллекции. Это происходит, если:

• Все ключи попадают в одну корзину (bucket) из-за плохой функции хеширования, что приводит к длинному списку или дереву в одной ячейке.
• Коллизии распределены неравномерно, и структура данных внутри корзины деградирует.

В Java 8 и выше, если в одной корзине слишком много элементов, HashMap преобразует связный список в сбалансированное дерево (TreeNode), что снижает худший случай до O(log n), но не до O(1).

Таким образом, операции становятся пропорциональны размеру коллекции при сильных коллизиях и плохом распределении хешей.