Как работает Dictionary: как вычисляется bucket и как влияет коллизия на производительность?

Question

Dictionary хранит элементы в массивах bucket’ов. Для ключа вычисляют хэш-код key.GetHashCode(), берут bucketIndex = hash % buckets.Length, и если в этом бакете уже есть запись, сравнивают ключи на равенство, переходя по связному списку (или дереву в новых версиях). При небольшой нагрузке lookup — O(1), но при многих коллизиях (одинаковых хэших) может деградировать до O(n) в худшем случае.

YeaHub · Accepted Answer

Хэширование:Получаем int hash = key.GetHashCode() & 0x7FFFFFFF (для неотрицательности).Индекс: bucket = hash % bucketCount.Структура bucket:int[] buckets хранит указатели на элементы в Entry[] entries.Каждый Entry содержит hashCode, key, value и next (индекс следующего при коллизии).Коллизии:Если уже есть Entry с тем же bucket, цепляем новый в начало списка.При поиске пробегаем цепочку, сравнивая hashCode и Equals(key).Производительность:При низкой загрузке (load factor ≈ 0.72) цепочки короткие → O(1).При высоких коллизиях длинные цепочки → O(k) где k — длина списка.Вывод:Стоит выбирать хорошие хэш-функции и поддерживать разумный размер Capacity для минимизации коллизий.

Как работает Dictionary<TKey, TValue>: как вычисляется bucket и как влияет коллизия на производительность?

Как работает Dictionary<TKey, TValue>: как вычисляется bucket и как влияет коллизия на производительность?