Сложность добавления в словарь O(1) — это всегда так или есть ситуации, когда это не так?

Добавление в dict имеет ожидаемую амортизированную сложность O(1), но не гарантированное постоянное время каждого вызова. Расширение таблицы, коллизии и стоимость пользовательских hash/eq меняют затраты.

При resize нужно перераспределить внутренние записи, что даёт дорогую отдельную операцию, распределяемую по последовательности вставок. Много одинаковых хешей заставляет выполнять дополнительные проверки равенства и может ухудшить поиск до линейного. Вычисление хеша сложного ключа тоже не обязательно O(1). Для обычных небольших ключей средняя модель полезна, но её нельзя выдавать за жёсткую гарантию задержки.