Всегда ли в словарях (Dictionary) сложность поиска O(1)?

Нет, не всегда. В худшем случае сложность поиска может деградировать до O(n). Dictionary<TKey, TValue> в .NET реализован как хеш-таблица, что в среднем дает амортизированную сложность O(1). Однако есть условия, при которых производительность падает.

Причины деградации до O(n):

1. Большое количество коллизий хеш-кодов: Если множество ключей возвращают одинаковый хеш-код, они помещаются в одну «корзину» (bucket), и поиск превращается в линейный обход списка.

   // АНТИПАТТЕРН: Все экземпляры BadKey будут иметь один хеш-код.
   public class BadKey
   {
       public int Id { get; set; }
       public override int GetHashCode() => 1; // Постоянный хеш!
   }

2. Плохая реализация GetHashCode() и Equals(): Для пользовательских типов-ключей эти методы должны быть корректно переопределены. GetHashCode() должен быть быстрым и давать равномерное распределение.

Как обеспечить близкую к O(1) сложность:

• Используйте в качестве ключей неизменяемые типы (например, string, int).
• Для кастомных ключей всегда переопределяйте GetHashCode() и Equals().
• Задавайте начальную емкость (capacity) конструктора словаря, если размер примерно известен, чтобы избежать частых рехеширований.
• Избегайте модификации ключа, пока он находится в словаре (это нарушит внутреннюю структуру).