Какая сложность добавления элемента в HashMap

Добавление элемента в HashMap в среднем имеет сложность O(1) (амортизированная константная сложность).

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

Пример:

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

Факторы, влияющие на сложность:

• Хорошая хеш-функция (минимизирует коллизии).
• Нагрузка (load factor) – при превышении threshold происходит рехеширование (увеличение размера массива корзин).