Как определяется временная сложность операции вставки элемента в HashMap?

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

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

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

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42); // вставка за O(1) в среднем