Какая скорость вставки в Dictionary

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

Пример:

d = {}
import timeit

# Вставка 1000 элементов
time = timeit.timeit(lambda: {i: i for i in range(1000)}, number=1000)
print(f"Время вставки 1000 элементов (1000 итераций): {time:.5f} сек")

Факторы, влияющие на скорость:

• Размер словаря (рехеширование при увеличении).
• Хеш-функция ключа (если хеш сложный, вставка замедлится).
• Коллизии (редко, но могут ухудшить производительность).

Для больших объемов данных можно предварительно задать размер через dict.fromkeys() или использовать defaultdict из collections.