Как устроен Dictionary изнутри
Вопрос
Расскажите, как устроен Dictionary<TKey, TValue> в .NET.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Два массива: buckets (индексы) и entries (хеш, next, ключ, значение)
Индекс бакета: хеш по модулю размера, размер простое число
Коллизии решаются цепочками через поле next внутри массива entries
Удалённые слоты собираются в free list и переиспользуются
При заполнении массивы растут примерно вдвое до простого числа с перехешированием
Не потокобезопасен: одновременная запись может сломать структуру
Что могут спросить следом
- Почему одновременная запись из двух потоков опасна, а не просто теряет данные?
- Что изменится, если GetHashCode всегда возвращает 0?
- Зачем FrozenDictionary в .NET 8?
Разбор
Внутри два массива. buckets хранит для каждого бакета индекс первой записи цепочки, а entries хранит сами записи: хеш-код, индекс следующей записи в цепочке, ключ и значение. Размер берётся простым числом.
При добавлении считается GetHashCode ключа, по модулю размера определяется бакет, дальше идём по цепочке через поле next и сравниваем ключи через Equals. Если ключа нет, запись добавляется в entries и становится головой цепочки. Удалённые записи не сдвигают массив, а уходят в список свободных слотов.
Когда записи заканчиваются, массивы увеличиваются примерно вдвое до следующего простого, и все записи перераспределяются по бакетам. Поэтому иногда Add стоит O(n), но в среднем O(1).
Словарь не потокобезопасен: параллельная запись может повредить цепочки, и раньше это приводило даже к зацикливанию при чтении. Для конкуренции есть ConcurrentDictionary, а для данных, которые только читают, в .NET 8 появился FrozenDictionary с оптимизированным поиском.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.