Какая алгоритмическая сложность удаления элемента в хеш-таблице

Удаление элемента в хеш-таблице в среднем имеет сложность O(1). Это связано с тем, что доступ к элементу происходит по ключу через хеш-функцию, которая вычисляет индекс за константное время.

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

Пример для JavaScript:

const map = new Map();
map.set('key', 'value');
map.delete('key'); // O(1) в среднем