Ответ
Удаление элемента в хеш-таблице в среднем имеет сложность O(1). Это связано с тем, что доступ к элементу происходит по ключу через хеш-функцию, которая вычисляет индекс за константное время.
В худшем случае (при коллизиях) сложность может быть O(n), если все элементы попали в одну корзину (ведро) и хранятся как связанный список. Однако при хорошей хеш-функции и правильном размере таблицы такие случаи редки.
Пример для JavaScript:
const map = new Map();
map.set('key', 'value');
map.delete('key'); // O(1) в среднемОтвет 18+ 🔞
Да ты посмотри, какая хуйня интересная получается! Вот берёшь ты, допустим, эту самую хеш-таблицу. И думаешь: "Ну, удалить элемент — это ж наверное, овердохуища операций, там пересчитывать всё, перестраивать..." Ан хуй там плавал!
Всё гениально, блядь, и просто, как три копейки. У тебя есть ключ. У тебя есть хеш-функция — этакая волшебная хуйня, которая из любого ключа делает число-индекс за одно и то же время, ну то есть O(1). Она твой ключ — хрясь! — и превращает в адресок конкретной корзины. Ты прибегаешь к этой корзине, хватаешь за шкирку нужный элемент и — выкидываешь его нахуй! Всё, приехали. В среднем — действительно O(1). Красота, ёпта!
Но, как всегда, есть одно "но", блядь, жирное такое "но". Это если твоя хеш-функция — говно, или таблицу ты раздул не по уму. Тогда начинается цирк. Все элементы, как бараны упрямые, лезут в одну и ту же корзину. И в этой корзине они уже не просто лежат, а висят связным списком, как гроздь бананов, сука. И чтобы найти нужный банан для удаления, приходится этот весь список, блядь, с начала до конца просматривать. Вот тут уже получается O(n), и волнение ебать, потому что n может быть овердохуищным.
Но! Не стоит, блядь, паниковать раньше времени. Если ты не совсем мудак и выбрал нормальную хеш-функцию, да ещё и размер таблицы адекватный, то такие пиздецовые коллизии — это как найти иголку в стоге сена, который ещё и горит. Редко, блядь, очень редко.
Смотри, как в JavaScript это выглядит, там всё прикрыто красивой обёрточкой:
const map = new Map();
map.set('key', 'value');
map.delete('key'); // O(1) в среднемВидишь? Создал, положил, удалил. Ни тебе мучений, ни страданий. Чистая магия, блядь. Главное — чтобы под капотом у этой магии не оказался, прости господи, один сплошной связанный список на все случаи жизни. А то будет не O(1), а "ой, ёбта, всё пропало".