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

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

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

Пример:

d = {}
d['key'] = 'value'  # O(1) в среднем

Причины ухудшения до O(n):

1. Много коллизий
2. Рехеширование при заполнении таблицы
3. Плохая хеш-функция (редко для встроенных типов Python)