Правильно ли, что при использовании стандартного словаря Python без переопределения хеш-функции практически не будет деградации операций до O(n)?

Нет: средняя O(1) у dict не исключает худшую O(n). Даже встроенные ключи могут иметь коллизии; рандомизация строковых хешей снижает некоторые атаки, но не отменяет теоретическую деградацию.

Стоимость операции зависит также от hash, eq, размера ключа и перераспределения таблицы. Пользовательская плохая хеш-функция — лишь один способ получить проблему. В обычной нагрузке деградация маловероятна, но говорить о гарантированной константности нельзя. Для недоверенного ввода ограничивайте размеры и измеряйте реальное поведение.