|
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) в случае коллизии.
Литература для изучения
← Previous topic
Initializing Elements in the Dictionary<TKey, TValue> Constructor in C#
Next topic →
How to convert IEnumerable to → Dictionary in C#<TKey, TValue> . Using the ToDictionary method
Your feedback ...
4
Comments
guest
17 January 2022 17:05
Спасибо, самая адекватная статья.
Читал до этого похожие статьи, но здесь самые понятные примеры, спасибо!
Спасибо за хорошие отзывы.
Когда я с опытом работы проходил собеседования по C# меня часто спрашивали про Dictionary
Чтобы поделиться и не забыть со временем подробности о Dictionary я добавил на сайт.
C# язык программирования мне очень нравится. Но пришлось немного :) писать и на других языках.
C# рекомендую изучать.
guest
30 October 2024 21:54
В статье написано, мол при добавлении нового значения и возникновении коллизии, старый Entry как-будто перемещается на свободное место, а на его место встает новый с новым значением. Немного просмотрел исходных код и кажется, что новое значение встает в свободное Entry, его поле next начинает указывать на старый Entry, а индекс в Bucket меняется на индекс нового созданного Entry. Могу ошибаться, но в других статьях тоже объясняется примерно так.
guest
(18 November 2024 10:11)
Согласен с вами
answer
guest
(19 September 2025 13:55)
Так и есть, статья вводит в заблуждение о том "Как устроен Dictionary"
answer
guest
(31 October 2025 19:56)
Не Согласен. Индекс считается по хеш коду. И этот алгоритм расчёта индекса не меняется. И по этому индексу должно быть записаны последние значения словаря из списка коллизий. И там же указывается в next новый индекс предыдущего значения по которому переписано старое значение. Если первое значение оставлять по тому же индексу то при коллизии мы всегда будем попадать на первое значение где next=null и цепочка коллизий будет обрываться. То есть мы не сможем разрешить коллизию.
answer
guest
(31 October 2025 20:02)
Если оставлять первое значение из списка коллизий по прежнему индексу, то мы постоянно должны менять поле next во всём списке значений , входящих в список коллизий при каждой новой коллизии
answer
New app for learning C# Debugging Code Data Types C# • C# data types: number (bool, char, byte, int, long, float, double, decimal), text (string), enumeration (enum), class (class), structure (struct)Storing objects in memory. Removing Objects from Memory C# type conversion Text in C# (type string and class String) DateTime in C# Enumerations in C # (enum) null try-catch Classes in C# (class) [bgcolor=#F5F9DB]Constructors for a class[/bgcolor] [bgcolor=#F5F9DB]Class Destructors[/bgcolor] [bgcolor=#F5F9DB]Inheritance[/bgcolor] [bgcolor=#F5F9DB]Inheritance using new[/bgcolor] [bgcolor=#F5F9DB]Inheritance using sealed[/bgcolor] [bgcolor=#F5F9DB]Abstract class[/bgcolor] [bgcolor=#F5F9DB]Constants and readonly [E_M_P_T_Y] fields in the classroom[/bgcolor] [bgcolor=#F5F9DB]Properties get and set in the classroom C# (accessors)[/bgcolor] [bgcolor=#F5F9DB]Operators, indexers in C#[/bgcolor] [bgcolor=#F5F9DB]Nested types in C#[/bgcolor] [bgcolor=#F5F9DB]Parameters in the C#[/bgcolor] class method [bgcolor=#F5F9DB]Generic methods, generic classes in C# (templates)[/bgcolor] [bgcolor=#F5F9DB]Converting a class object from one type to another[/bgcolor] [bgcolor=#F5F9DB]Class object in C#[/bgcolor] [bgcolor=#F5F9DB]Static constructor and static properties and methods[/bgcolor] [bgcolor=#F5F9DB]Additional class features in C#[/bgcolor] [bgcolor=#F5F9DB]Class naming conventions in C#[/bgcolor] Static Class Anonymous Class Interfaces Struct structure [bgcolor=#F5F9DB]Converting a struct object from one type to another[/bgcolor] Lazy class loading in C# Tuples Dynamic objects with any properties Arrays Collection • What are generic (typed) collections in C#? The classes are List<T>, SortedList<T>, Stack<T>, Dictionary<TKey, TValue>, LinkedList<T>, Queue<T>, HashSet<T>, SortedSet<T>, ConcurrentDictionary<TKey, TValue>, SortedDictionary<TKey, TValue>Non-generic collection classes (different types of items are stored in the same collection) ArrayList class (collection in C#) SortedList class (collection in C#) Stack class (collection in C#) Queue class (collection in C#) Hashtable class (collection in C#) BitArray class (collection in C#) Generic, typed collection classes in C# (elements of the same type are stored in the same collection) List class<T> (typed collection in C#) LinkedList class<T> (typed collection in C#) SortedList<TKey, TValue> class (typed collection in C#) Stack class<T> (typed collection in C#) Queue class<T> (typed collection in C#) HashSet class<T> (typed collection in C#) SortedSet class<T> (typed collection in C#) ObservableCollection class<T> (typed collection in C#) Dictionary<TKey, TValue> class (typed collection in C#) SortedDictionary<TKey, TValue> class (typed collection in C#) ConcurrentDictionary<TKey, TValue> class (typed collection in C#) Asymptotic complexity for adding, removing, taking an item in collections • Asymptotic complexity for adding, removing, taking an element in collections C# (List, SortedList, Stack, Dictionary, LinkedList, Queue, HashSet, SortedSet, ConcurrentDictionary, SortedDictionary)Sorting Elements in the [] Array and List <T>Collection My implementation of IEnumerator, IEnumerable, and iterators Extension Methods for IEnumerable<T> (Search, Replace, Value Sampling) in C# Sorting, filtering in LINQ (Language-Integrated Query) Pointers Working with files Serialization Namespaces Delegate Universal Delegates Events Lyamda Regular expressions Regular Expressions in C# Process, process modules Threads, multithreading Parallel Library Task (TPL) Asynchronous methods (async and await) Application domains Attributes Reflection in C# Preprocessor directives (if on compilation) What is the CLR assembly and runtime? Creating and connecting our build ▷ Database in Console Application C# DI Dependency Injection in C# Convenient Visual Studio utilities exe to C# code In a C# application, call the C++ functions Additional topics, questions The checked and unchecked math operators Additional C# classes It"s time Encryption Excell WWW Sites to Learn C#
|