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

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

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

Пример добавления:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 10); // O(1) в среднем

Важные детали (Java 8+):

• При большом количестве коллизий в одной корзине (TREEIFY_THRESHOLD = 8) связный список преобразуется в красно-черное дерево, уменьшая худший случай до O(log n).
• На сложность влияют начальная ёмкость (capacity) и коэффициент загрузки (load factor, по умолчанию 0.75). При превышении порога происходит рехеширование (rehashing) — увеличение размера массива корзин.