Яка складність видалення елемента в хеш-таблиці?

Середня часова складність видалення елемента в хеш-таблиці - O(1).

Чому так:

1. Хеш-функція обчислює індекс комірки за постійний час.
2. Таблиця одразу звертається до потрібного кошика (bucket).
3. Елемент видаляється напряму, без обходу всієї структури.

Але в найгіршому випадку: Якщо в кошику виникло багато колізій (наприклад, у ньому зберігається довгий список), доведеться пройти всі елементи в цьому кошику, і тоді видалення займе O(n).

Підсумок:

• Середня складність: O(1)
• Найгірша: O(n)
• При нормальному навантаженні (load factor < 0.75) і хорошій хеш-функції: видалення майже завжди відбувається миттєво.