Какое время вставки элемента в HashMap

Вставка элемента в HashMap в среднем занимает O(1) времени (амортизированная сложность). Однако, в худшем случае (например, при коллизиях и превращении списка в дерево) сложность может достигать O(log n) для Java 8+ (из-за использования красно-черного дерева в корзинах).

Пример:

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

Нюансы:

1. При рехешинге (увеличении размера таблицы) вставка временно замедляется (O(n)).
2. Если хеш-функция плохая, коллизии учащаются, ухудшая производительность.
3. В Java 8+ при большом количестве коллизий корзина переключается со связного списка (O(n)) на дерево (O(log n)).