В какой ситуации поиск по словарю может деградировать до худшего случая?

Поиск в хеш-словаре может замедлиться при большом числе коллизий, дорогом сравнении ключей или плохо реализованном hash. Средняя O(1) не гарантирует худший случай.

Если множество ключей попадает в конфликтующие позиции, проверяется больше кандидатов. Пользовательский eq тоже может быть дорогим или иметь нежелательные побочные эффекты.

Не используйте нестабильный хеш изменяемого содержимого. Для внешних данных учитывайте защиту runtime, но не считайте её доказательством постоянного времени любой операции.