Как устроена коллекция Dictionary в C#?
Что проверяют
Знает ли кандидат внутреннее устройство хеш-таблицы .NET (два массива, а не список объектов в ячейке), роль GetHashCode и Equals и последствия изменяемого ключа.
Как отвечать
Dictionary<TKey, TValue> это хеш-таблица на двух массивах: buckets хранит индекс первой записи бакета, entries хранит сами записи со структурой hashCode, next, key, value. Цепочка коллизий это связный список по индексам внутри массива entries, а не набор объектов-узлов: меньше аллокаций и лучше локальность памяти.
Как проходит вставка: считается comparer.GetHashCode(key), из хеша вычисляется номер бакета (размер таблицы простое число, остаток берётся быстрым делением), запись кладётся в свободный слот entries и встаёт в голову цепочки.
Поиск: тот же бакет, проход по цепочке, сравнение сначала сохранённого хеша (дёшево), затем Equals. Средняя сложность O(1), худшая O(n) при вырожденной хеш-функции. Дерева при длинных цепочках, в отличие от Java, здесь нет.
Рост и удаление:
- при заполнении массива ёмкость увеличивается примерно вдвое до следующего простого числа, все записи перераспределяются. Если размер известен заранее, стоит передать его в конструктор и не платить за серию расширений;
- удаление освобождает слот и кладёт его в список свободных, следующий
Addего переиспользует.
Сравнение ключей берётся из EqualityComparer<TKey>.Default либо из IEqualityComparer<TKey>, переданного в конструктор. Реализовывать IEquatable<T> не обязательно, но она избавляет от упаковки и виртуального вызова object.Equals. Для строковых ключей .NET стартует с быстрого нерандомизированного компаратора и переключается на рандомизированное хеширование, если цепочки становятся слишком длинными: защита от намеренного подбора коллизий.
Контракт ключа: равные объекты обязаны давать равный хеш, а сам хеш обязан быть стабильным. Изменяемый ключ, отредактированный после вставки, теряется: элемент в словаре есть, но TryGetValue его не находит.
Практика: порядок перечисления не гарантирован, полагаться на него нельзя. Класс не потокобезопасен даже в сценарии «много читателей и один писатель», для конкурентного доступа ConcurrentDictionary. Читать лучше через TryGetValue, это один поиск вместо двух в связке ContainsKey плюс индексатор.
Где спотыкаются
Описывают ячейку как список объектов и говорят про удвоение до степени двойки. На вопрос, что будет, если изменить объект-ключ после вставки, отвечают, что ничего не сломается.