Какова временная сложность операции удаления элемента из HashMap?

Средняя сложность — O(1), в худшем случае — O(n).

Процесс удаления:

1. Вычисление хэша ключа: O(1).
2. Определение бакета (корзины): O(1).
3. Поиск элемента внутри бакета:
   • O(1) — если элементы хранятся в связном списке (при малом количестве коллизий).
   • O(log n) — если бакет преобразован в сбалансированное дерево (при большом количестве коллизий, начиная с Java 8).
4. Удаление узла: O(1).

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

Пример на Java:

import java.util.HashMap;
import java.util.Map;

public class Example {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 10);
        map.put("banana", 20);

        // Удаление элемента — в среднем O(1)
        Integer removedValue = map.remove("apple");
        System.out.println("Removed: " + removedValue); // Removed: 10
    }
}

Ключевой момент: Эффективность HashMap напрямую зависит от качества хэш-функции и коэффициента загрузки (load factor).