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

В среднем O(1), в худшем случае O(n) при коллизиях. Удаление включает:

1. Вычисление хэша ключа (O(1))
2. Нахождение бакета (O(1))
3. Поиск элемента в бакете (O(1) для LinkedList или O(log n) для TreeBin в Java 8+)
4. Удаление узла (O(1))

Пример:

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

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