Какая алгоритмическая сложность поиска в словаре

Что проверяют

Понимаете ли вы, как устроен Dictionary<TKey,TValue> и от чего зависит обещанное O(1). Интервьюер ждёт средний и худший случай, а затем практику: TryGetValue, требования к ключу, выбор между словарями .NET. Частый уточняющий вопрос: что будет с ключом-структурой без переопределённого GetHashCode.

Как отвечать

• поиск: TryGetValue, ContainsKey и индексатор в среднем работают за O(1). По GetHashCode вычисляется корзина, внутри сравнение через Equals;
• худший случай: O(n), когда много ключей даёт один хэш. Внутри .NET это цепочки, но не из объектов-узлов, а из индексов в массиве entries, что экономит память;
• расширение: при заполнении массив растёт примерно вдвое до ближайшего простого размера с перехэшированием всех записей. Одна такая вставка стоит O(n), в среднем O(1). Если размер известен, передайте capacity в конструктор;
• сравнение ключей: через IEqualityComparer<TKey>, по умолчанию EqualityComparer<TKey>.Default, для строк без учёта регистра StringComparer.OrdinalIgnoreCase.

Хэши строк в современном .NET рандомизированы на каждый процесс, поэтому GetHashCode строки нельзя сохранять в базу или передавать между сервисами.

Полезно показать, что знаете альтернативы и их цену:

• SortedDictionary: красно-чёрное дерево, O(log n), зато ключи упорядочены;
• SortedList: поиск бинарный, O(log n), вставка в середину O(n);
• FrozenDictionary: появился в .NET 8, неизменяемый словарь, оптимизированный под частое чтение.

Где спотыкаются

Пишут if (dict.ContainsKey(k)) v = dict[k];. Это два поиска там, где хватит одного TryGetValue, а обращение индексатором к отсутствующему ключу бросает KeyNotFoundException.

Делают ключом свою структуру без Equals и GetHashCode. Реализация по умолчанию из ValueType может работать через рефлексию и давать много коллизий. Решение: переопределить оба метода, реализовать IEquatable<T> или взять record struct.

Ищут по значению через ContainsValue или LINQ FirstOrDefault и считают это поиском в словаре. Это полный перебор O(n); если такой поиск частый, нужен второй словарь в обратную сторону.