|
buckets
| bucketNum=0 |
| bucketNum=1 |
| bucketNum=2 |
| bucketNum=3 |
|
entries
| hashCode | 43 |
| key | MyKey { Name = "Вася", Age = 45 } |
| value | 60.3 |
| next | null |
| hashCode | 73 |
| key | MyKey {Name = "Евгений", Age = 36} |
| value | 62.2 |
| next | null |
| hashCode | |
| key | |
| value | |
| next | null |
| hashCode | |
| key | |
| value | |
| next | null |
|
добавим новый key value в dictionary
C#
Код из примера
MyKey myKey3 = new MyKey() { Name = "Петя", Age = 45 };
myDict.Add(myKey3, 71.6f);
hashCode = длина строки("Петя") * 10 + 3
hashCode = 4 * 10 + 3
hashCode = 43
hashCode = 43
по прежнему capacity = 4
int bucketNum = 43 % 4;
int bucketNum = 3;
bucketNum = 3
bucket[bucketNum] уже занята и это коллизия
мы не можем записать
| hashCode | 43 |
| key | MyKey { Name = "Петя", Age = 45 } |
| value | 71.6 |
| next | null |
на
| hashCode | 43 |
| key | MyKey { Name = "Вася", Age = 45 } |
| value | 60.3 |
| next | null |
поэтому для решения колизии
мы меняем только entries
1) ищем свободный entries и туда записываем старый Entry
| hashCode | 43 |
| key | MyKey { Name = "Вася", Age = 45 } |
| value | 60.3 |
| next | null |
2) по высчитанному индексу записываем новый key value
и меняем next
| hashCode | 43 |
| key | MyKey { Name = "Петя", Age = 45 } |
| value | 71.6 |
| next | индекс в таблице Entry где находится старый Entry |
вот что получилось:
|
buckets
| bucketNum=0 |
| bucketNum=1 |
| bucketNum=2 |
| bucketNum=3 |
|
|
entries
| hashCode | 43 |
| key | MyKey { Name = "Петя", Age = 45 } |
| value | 71.6 |
| next | 2 |
| hashCode | 73 |
| key | MyKey {Name = "Евгений", Age = 36} |
| value | 62.2 |
| next | null |
| hashCode | 43 |
| key | MyKey { Name = "Вася", Age = 45 } |
| value | 60.3 |
| next | null |
| hashCode | |
| key | |
| value | |
| next | null |
|
Этот метод для решения коллизий называется метод цепочек
Когда коллекция entries полностью заполнена (нет пустых), тогда коллекции entries и bucket пересоздаются на новый размер и перехешурется entries.
На заметку!
Сложность добавления элемента O(1) или O(n) в случае коллизии.
Удаление элемента
При удалении элемента мы затираем его содержимое значениями по умолчанию
меняем указатели next других элементов при неоходимости
Сложность O(1) или O(n) в случае коллизии.
При очистке всего dictionary, его внутренний размер не изменяется.
Взять значение по ключу
Сложность O(1) или O(n) в случае коллизии.
Литература для изучения
← Предыдущая тема
Инициализация элементов в конструкторе Dictionary<TKey, TValue> в C#
Следующая тема →
Как в C# сконвертировать IEnumerable в → Dictionary<TKey, TValue> . Используем метод ToDictionary
Ваши Отзывы ...
4
комментариев
гость
17 января 2022 17:05
Спасибо, самая адекватная статья.
Читал до этого похожие статьи, но здесь самые понятные примеры, спасибо!
Спасибо за хорошие отзывы.
Когда я с опытом работы проходил собеседования по C# меня часто спрашивали про Dictionary
Чтобы поделиться и не забыть со временем подробности о Dictionary я добавил на сайт.
C# язык программирования мне очень нравится. Но пришлось немного :) писать и на других языках.
C# рекомендую изучать.
гость
30 октября 2024 21:54
В статье написано, мол при добавлении нового значения и возникновении коллизии, старый Entry как-будто перемещается на свободное место, а на его место встает новый с новым значением. Немного просмотрел исходных код и кажется, что новое значение встает в свободное Entry, его поле next начинает указывать на старый Entry, а индекс в Bucket меняется на индекс нового созданного Entry. Могу ошибаться, но в других статьях тоже объясняется примерно так.
гость
(18 ноября 2024 10:11)
Согласен с вами
ответить
гость
(19 сентября 2025 13:55)
Так и есть, статья вводит в заблуждение о том "Как устроен Dictionary"
ответить
гость
(31 октября 2025 19:56)
Не Согласен. Индекс считается по хеш коду. И этот алгоритм расчёта индекса не меняется. И по этому индексу должно быть записаны последние значения словаря из списка коллизий. И там же указывается в next новый индекс предыдущего значения по которому переписано старое значение. Если первое значение оставлять по тому же индексу то при коллизии мы всегда будем попадать на первое значение где next=null и цепочка коллизий будет обрываться. То есть мы не сможем разрешить коллизию.
ответить
гость
(31 октября 2025 20:02)
Если оставлять первое значение из списка коллизий по прежнему индексу, то мы постоянно должны менять поле next во всём списке значений , входящих в список коллизий при каждой новой коллизии
ответить
Новое приложение для изучения C# Отладка кода Типы данных C# • C# типы данных: число (bool, char, byte, int, long, float, double, decimal), текст (string), перечисление (enum), класс (class), структура (struct)Хранение объектов в памяти. Удаление объектов из памяти C# конвертация типов Текст в C# (тип string и класс String) DateTime (дата и время) в C# Перечисления в C# (enum) null try-catch Классы в C# (class) Конструкторы для класса Деструкторы для класса Наследование Наследование с использованием new Наследование с использованием sealed Абстрактный класс Константы и readonly поля в классе Свойства get и set в классе C# (аксессоры) Операторы, индексаторы в C# Вложенные типы в C# Параметры в методе класса C# Универсальные методы, универсальные классы в C# (шаблоны) Преобразование объекта класса из одного типа в другой Объект класса в C# Статический конструктор и статические свойства и методы Дополнительные возможности класса в C# Правила именования классов в C# Статический класс Анонимный класс Интерфейсы Структура struct Преобразование объекта структуры из одного типа в другой Отложенная загрузка class Lazy в C# Кортежи (tuple) Динамические объекты с любыми свойствами Массивы Коллекции • Что такое обобщенные (типизированные) коллекции в C# ? Классы List<T>, SortedList<T>, Stack<T>, Dictionary<TKey,TValue>, LinkedList<T>, Queue<T>, HashSet<T>, SortedSet<T>, ConcurrentDictionary<TKey, TValue>, SortedDictionary<TKey, TValue>Классы необобщенных коллекций (в одной коллекции хранятся элементы разного типа) Класс ArrayList (коллекция в C#) Класс SortedList (коллекция в C#) Класс Stack (коллекция в C#) Класс Queue (коллекция в C#) Класс Hashtable (коллекция в C#) Класс BitArray (коллекция в C#) Классы обобщенных, типизированных коллекций в C# (в одной коллекции хранятся элементы одного типа) Класс List<T> (типизированная коллекция в C#) Класс LinkedList<T> (типизированная коллекция в C#) Класс SortedList<TKey, TValue> (типизированная коллекция в C#) Класс Stack<T> (типизированная коллекция в C#) Класс Queue<T> (типизированная коллекция в C#) Класс HashSet<T> (типизированная коллекция в C#) Класс SortedSet<T> (типизированная коллекция в C#) Класс ObservableCollection<T> (типизированная коллекция в C#) Класс Dictionary<TKey, TValue> (типизированная коллекция в C#) Класс SortedDictionary<TKey, TValue> (типизированная коллекция в C#) Класс ConcurrentDictionary<TKey, TValue> (типизированная коллекция в C#) Асимптотическая сложность для добавления, удаления, взятия элемента в коллекциях • Асимптотическая сложность для добавления, удаления, взятия элемента в коллекциях C# (List, SortedList, Stack, Dictionary, LinkedList, Queue, HashSet, SortedSet, ConcurrentDictionary, SortedDictionary)Сортировка элементов в массиве [] и коллекции List Моя реализация IEnumerator, IEnumerable и итераторы Методы расширения для IEnumerable (поиск, замена, выборка значений) в C# Сортировка, фильтрация в LINQ (Language-Integrated Query) Указатели Работа с файлами Сериализация Пространства имен Delegate Универсальные делегаты События Лямда Регулярные выражения Регулярные выражения в C# Процесс, модули процесса Потоки, многопоточность Parallel Library Task (TPL) Параллельное программирование задач Асинхронные методы (async и await) Домены приложений Атрибуты Рефлексия (отражение) reflection в C# Директивы препроцессора (if при компиляции) Что такое сборка и исполняющая среда CLR ? Создание и подключение нашей сборки ▷ База данных в консольном приложении C# Внедрение зависимостей (Dependency Injection) DI в C# Удобные утилиты Visual Studio exe to C# code В приложении C# вызываем C++ функции Дополнительные темы, вопросы Математические операторы checked и unchecked Дополнительный C# классы Время Шифрование / Cryptography Excell WWW сайты для изучения C#
|