Ответ
В среднем, добавление элемента в HashMap занимает O(1) (константное время), если хеш-функция хорошо распределяет элементы и нет коллизий.
При коллизиях (когда несколько ключей попадают в одну корзину) время может ухудшиться до O(n) в худшем случае (если все ключи попадают в одну корзину).
С Java 8 при большом количестве коллизий HashMap заменяет связанный список на сбалансированное дерево, уменьшая худший случай до O(log n).
Пример добавления:
val map = HashMap<String, Int>()
map["key"] = 42 // ~O(1)