Qual é a complexidade temporal de inserir um novo elemento na estrutura de dados HashMap?

Временная сложность вставки нового элемента в HashMap в среднем случае — O(1). Это достигается за счёт использования хеш-функции, которая вычисляет индекс корзины (bucket) для хранения элемента.

Однако в худшем случае, когда происходит много коллизий и элементы попадают в одну корзину, сложность может деградировать до O(n), где n — количество элементов в HashMap.

Современные реализации Java HashMap (начиная с Java 8) при большом числе коллизий преобразуют связанные списки в сбалансированные деревья, что улучшает худший случай до O(log n).

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