Какова сложность поиска, добавления и удаления элементов в dict и set?

Основы хеш-таблиц

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

Сложность операций

• Поиск: O(1) в среднем, O(n) в худшем случае при большом количестве коллизий.
• Добавление: O(1) в среднем, но может быть O(n) при перехешировании (resize) таблицы.
• Удаление: O(1) в среднем, O(n) в худшем случае.

Пример кода

d = {}
d['key'] = 'value'  # O(1)
print(d['key'])     # O(1)
del d['key']        # O(1)

s = {1, 2, 3}
s.add(4)            # O(1)
print(2 in s)       # O(1)
s.remove(3)         # O(1)

Вывод

Понимание сложности операций dict и set помогает выбирать правильные структуры данных для оптимизации производительности, особенно при работе с большими объемами данных.