Какова временная сложность вставки элемента в HashMap в самом неблагоприятном случае?

Временная сложность вставки элемента в HashMap в Java в среднем составляет O(1), но в самом неблагоприятном случае может достигать O(n).

Неблагоприятный случай возникает, когда все ключи попадают в одну корзину (bucket), то есть у них одинаковый хэш-код или коллизии распределены плохо. В этом случае HashMap ведёт себя как связный список (или с Java 8 — как сбалансированное дерево), и вставка требует перебора элементов в этой корзине.

С Java 8, если количество элементов в корзине превышает определённый порог, структура меняется с списка на красно-чёрное дерево, что улучшает худший случай до O(log n).

Итого:

• Средний случай: O(1)
• Худший случай до Java 8: O(n)
• Худший случай с Java 8 и выше: O(log n)