Какая сложность операций с хеш-таблицей?

Операции с хеш-таблицей (объект, Map, Set) — вставка, поиск и удаление — в среднем выполняются за O(1), а в худшем случае за O(n).

Средняя сложность: O(1)

Хеш-таблица вычисляет по ключу хеш и обращается к нужной «ячейке» напрямую — без перебора:

const map = new Map();
map.set('key', 'value'); // O(1) вставка
map.get('key');          // O(1) поиск
map.delete('key');       // O(1) удаление
map.has('key');          // O(1) проверка

Это делает хеш-таблицу идеальной для быстрого доступа по ключу.

Худший случай: O(n)

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

Пространственная сложность

O(n) — нужно хранить все элементы плюс накладные расходы на таблицу.

Сравнение

• Массив: доступ по индексу O(1), но поиск по значению O(n).
• Хеш-таблица: доступ/поиск по ключу O(1) в среднем.
• Поэтому для проверки наличия set.has(x) (O(1)) быстрее array.includes(x) (O(n)).

Коротко для собеседования

Хеш-таблица (объект, Map, Set): вставка/поиск/удаление в среднем O(1) за счёт хеширования ключа, в худшем O(n) при коллизиях. Память O(n). Поэтому поиск по ключу/has быстрее перебора массива — используют для быстрого доступа и дедупликации.