Какая сложность вставки при коллизии в HashMap

Вставка элемента в HashMap при коллизии имеет среднюю сложность O(1), но в худшем случае (если все ключи попадают в один бакет) — O(n), где n — количество элементов в бакете.

При коллизии элементы хранятся в виде связанного списка (до Java 8) или сбалансированного дерева (Java 8+ при большом количестве коллизий).

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);  // O(1)  
map.put("b", 2);  // O(1)  
map.put("a", 3);  // Коллизия, но O(1) – замена значения  
map.put("c", 4);  // O(1)  

Если хеш-функция плохая и все ключи попадают в один бакет, сложность вставки деградирует до O(n).