Whether in actual projects or during our learning process, we will focus on the storage type Dictionary<TKey, TValue>. Each addition to Dictionary<TKey, TValue> contains a value and the key associated with it. The use of keys is very fast to retrieve values, close to O (1) because the Dictionary<TKey, TValue> class is implemented as a hash table. First, let's start with a simple example. The following is the creation and assignment of a dictionary.
Dictionary<int, string> openWith = new Dictionary<int, string>(); (1000, "Key value is 1000"); (1001, "Key value is 1001");
I believe most developers are not unfamiliar with the above examples, so what is the implementation principle of Dictionary<TKey, TValue>? What is the implementation principle of initialization, assignment, value acquisition and capacity expansion in the dictionary? Many times we need to know the truth, and even more so we need to know the reason. Next, we will carefully understand the data structure of its memory, the logic of value acquisition, and the expansion principle. Then we will follow the implementation source code of Dictionary<TKey, TValue> in CoreFX to do a simple learning and thinking. We need to pay special attention to this:
When learning and analyzing source code, do not take preconceptions. Interpret according to the logic of the framework and source code, record the key analysis of the parts you don’t understand, and finally connect the entire logic. If we set the logic to A-B-C at the beginning, but when we read a stage, we find that it has become C-B-A, we cannot continue at this time because there will be many factors causing local adjustments in the specific implementation process. After the interpretation is completed, we can compare the actual logic with the differences in the logic understood by our personal early stage, find out the reasons and analyze it.
1. Dictionary<TKey, TValue> Initialization
There are many construction methods for Dictionary<TKey, TValue>. Let’s take a look at the basic implementation methods. First, let’s take a look at the corresponding source code (the unnecessary parts of the source code have been partially deleted, and the core implementation logic has been retained).
public Dictionary(int capacity, IEqualityComparer<TKey>? comparer)
{
if (capacity > 0) Initialize(capacity);
if (!typeof(TKey).IsValueType)
{
_comparer = comparer ?? EqualityComparer<TKey>.Default;
if (typeof(TKey) == typeof(string) && (_comparer!) is IEqualityComparer<string> stringComparer)
{
_comparer = (IEqualityComparer<TKey>)stringComparer;
}
}
else if (comparer is not null && comparer != EqualityComparer<TKey>.Default)
{
_comparer = comparer;
}
}The above implementation logic focuses on two parts. The first part: initializing the capacity of Dictionary<TKey, TValue>; the second part is initializing the IEqualityComparer? comparison of Dictionary<TKey, TValue>. The focus of this article is to analyze the storage structure of Dictionary<TKey, TValue>, which involves the implementation logic of the comparator, which will be introduced in subsequent chapters.
Let’s take a look at the implementation logic of Initialize() for a brief introduction. First, let’s take a look at the corresponding source code implementation (the unnecessary parts have been deleted, so that everyone can view them intuitively).
private int Initialize(int capacity)
{
int size = (capacity);
int[] buckets = new int[size];
Entry[] entries = new Entry[size];
_freeList = -1;
#if TARGET_64BIT
_fastModMultiplier = ((uint)size);
#endif
_buckets = buckets;
_entries = entries;
return size;
}From the above source code, we can see that the corresponding relevant capacity size of the dictionary is set according to the incoming capacity parameters, which includes two parts. The first part: Calculate the corresponding buckets and entries sizes according to the set capacity size. Regarding why the two array structures of buckets and entries are used, we will focus on the next section; the second part: judge the number of bits of the current machine and calculate the corresponding _fastModMultiplier. Let's take a look at the computing logic of (capacity). (The corresponding type of this class is defined as: internal static partial class HashHelpers)
public static int GetPrime(int min)
{
foreach (int prime in Primes)
{
if (prime >= min) return prime;
for (int i = (min | 1); i < ; i += 2)
{
if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i;
}
return min;
}
}HashHelpers is used to calculate and maintain the prime values of the hash table capacity. Why does the hash table need to use prime numbers? Mainly to reduce the occurrence of hash collisions, the selection of prime numbers can reduce common factors and reduce the possibility of hash collisions. In addition, selecting prime numbers can also ensure that excessive duplication is not prone to occur when the capacity of the hash table changes. If the capacity is selected as a composite (non-prime), then when the capacity changes, the new capacity may have the same factor as the old capacity, increasing the risk of hash conflicts.
Next, we look at the calculation logic of the entire hash table capacity along the call relationship of GetPrime(). HashHelpers sets a read-only prime array of Primes[]. The specific elements are as follows. As for what to use such prime arrays, these prime numbers have been proven to be effective in practice, suitable for many common usage scenarios, and more to help provide better performance in data structures such as hash tables.
internal static ReadOnlySpan<int> Primes => new int[]
{
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
};GetPrime() will first cycle Primes[] to determine the relationship between the set min size and the elements of the prime number table. If the elements in the prime number table are greater than min, then the corresponding prime number will be directly used without subsequent calculations. If the set min is not in the predetermined prime number table, the prime number will be calculated. Regarding the calculation logic of prime numbers, the definition and assignment of Dictionary<TKey, TValue> at the beginning of this article will be explained. First, min and 1 are bitwise or operations. When the capacity is not assigned during the initialization process, (min | 1) is 1. The i value after bitwise operation meets the definition of prime numbers, and then ((i - 1) % HashPrime != 0) operation, where HashPrime = 101 is used as a prime factor in the hash algorithm (101 is a relatively small prime number, which can reduce the possibility of hash collisions and is more efficient when calculating hash). For the initialization of Dictionary<TKey, TValue> with no capacity set, the capacity obtained by calculation is int size=3. (i.e. 3*4*8=72(bit))
(Note: For Dictionary with capacity set, calculate the corresponding size value according to the above logic. I won't go into too much introduction here)
After the calculation is obtained, set the free list to -1 (_freeList = -1). Classification is performed according to the number of bits of the machine running at compile time. If the machine is not 64 bits, the two arrays of buckets and entries are initialized. If the machine is 64 bits, it is necessary to recalculate and obtain _fastModMultiplier, and its calculation logic is as follows:
public static ulong GetFastModMultiplier(uint divisor) => / divisor + 1;
The above calculation results return the approximate reciprocal of the divisor and calculate the multiplication factor used for fast modulus calculation.
Through the above calculation process, we can have a simple understanding of the capacity calculation of Dictionary<TKey, TValue>. Next, let’s take a look at the two arrays used to store data and hash indexes in detail.
2. The storage infrastructure of Dictionary<TKey, TValue>
Let's analyze the two important array buckets and entries of Dictionary<TKey, TValue> in detail. First, let’s take a look at the actual data structure of Entry[]?_entries:
private struct Entry
{
public uint hashCode;
public int next;
public TKey key;
public TValue value;
}The structure in which data is actually stored in Dictionary<TKey, TValue> is Entry[], where each element of the array is an Entry, which is a structure, which is used to store the information of each key-value pair within the hash table. The defined key and value are the key-value pairs we add when setting the dictionary. Therefore, the other two attributes need to be analyzed with a focus.
hashCode is the hash value obtained when adding a key. During the hash value calculation process, the key needs to be calculated by category. The hash value calculation logic of numerical types, strings, structures, and objects in C# is different. The hash value calculation logic for "numerical types" is "the hash code generation logic for numerical types is usually to convert the value of numerical types into integers, and then use the integer as hash code. "The hash value calculation logic for strings is "The default string hash code calculation method uses the so-called "Jenkins One-at-a-Time Hash" algorithm. "The hash value calculation logic for structures and objects will not be introduced in detail.
next is usually used to handle hash collisions, i.e. cases where multiple keys have the same hash code. next is an index pointing to the next element in the hash table with the same hash code. Where next=-1 means the end of the linked list; next=-2 means the end of the free list, next=-3 means the index 0 on the free list, next=-4 means the index 1 on the free list, and so on.
Entry reduces memory overhead by using structs instead of classes, because structs are value types and classes are reference types. Structures are allocated on the stack, while classes are allocated on the heap.
The above introduces the structure of Entry and the corresponding attribute fields. Next, let's take a look at the structure and calculation logic of int[] buckets. buckets is a simple array of int type. Such arrays are usually used to store information of hash buckets. Each bucket is actually an index pointing to a linked list or header of a linked list, used to resolve hash conflicts.
private ref int GetBucket(uint hashCode)
{
int[] buckets = _buckets!;
#if TARGET_64BIT
return ref buckets[(hashCode, (uint), _fastModMultiplier)];
#else
return ref buckets[(uint)hashCode % ];
#endif
}GetBucket() is used to obtain the bucket index in the hash table, where the parameter hashCode is the hash code corresponding to the key. Under the 64-bit target architecture, the method is used for fast modulus operations, and under the 32-bit target architecture, the ordinary modulus operations are used. So why maintain a bucket for storing hash tables in Dictionary<TKey, TValue>? It mainly has the following 4 purposes:
(1) Resolve hash conflicts: Two or more different keys obtain the same hash code through the hash function, resulting in them being stored in the same location in the hash table. By using buckets, multiple elements can be stored in the same location, solving the problem of hash conflict.
(2) Provide quick search: calculate the hash code of the key through the hash function, and then store the element in the bucket of the hash table. You can locate the position where the element is stored within a constant time (on average), to achieve quick search.
(3) Support efficient insertion and deletion: When inserting an element, determine the bucket that the element should store through a hash function, and then add it to the bucket's linked list or other data structure. When an element is deleted, you can also quickly locate the bucket that stores the element and delete the element.
(4) Balancing load: The performance of the hash table is related to the load factor, and the load factor is the ratio of the number of elements to the number of buckets. Using the right number of buckets can help balance the load, preventing the hash table from becoming overcrowded, thus maintaining its performance. Different hash table implementations may use different data structures, such as linked lists, trees, etc. C#'s Dictionary uses an int[] to maintain the bucket index of this hash table.
3. Implementation of TryAdd for Dictionary<TKey, TValue>
The above mainly introduces the initialization of Dictionary<TKey, TValue>, the storage of data corresponding to the storage structure and the hash table bucket index. Now let’s take a look at the implementation method of adding elements of Dictionary<TKey, TValue>. The following is a simplified implementation code of C# and deletes the part that is not currently concerned.
In this example, the value assigned to the key is an integer type, and some of them are deleted for non-numeric types, debugging code, etc. (Because the logic of objects or setting up comparator is relatively cumbersome, it will be introduced below)
private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
{
Entry[]? entries = _entries;
uint hashCode = (uint) () ;
uint collisionCount = 0;
ref int bucket = ref GetBucket(hashCode);
int i = bucket - 1;
int index;
if (_freeCount > 0)
{
index = _freeList;
_freeList = StartOfFreeList - entries[_freeList].next;
_freeCount--;
}
else
{
int count = _count;
if (count == )
{
Resize();
bucket = ref GetBucket(hashCode);
}
index = count;
_count = count + 1;
entries = _entries;
}
ref Entry entry = ref entries![index];
= hashCode;
= bucket - 1;
= key;
= value;
bucket = index + 1;
_version++;
return true;
}The core of the implementation logic in the above source code contains three parts, namely, calculating hashCode, calculating hash table bucket index, and Dictionary expansion. The first two implementation logics have been introduced in the previous section. This section focuses on the expansion logic of Dictionary<TKey, TValue>. Let's take a look at the implementation logic of Resize().
private void Resize() => Resize((_count), false);
private void Resize(int newSize, bool forceNewHashCodes)
{
Entry[] entries = new Entry[newSize];
int count = _count;
(_entries, entries, count);
_buckets = new int[newSize];
#if TARGET_64BIT
_fastModMultiplier = ((uint)newSize);
#endif
for (int i = 0; i < count; i++)
{
if (entries[i].next >= -1)
{
ref int bucket = ref GetBucket(entries[i].hashCode);
entries[i].next = bucket - 1;
bucket = i + 1;
}
}
_entries = entries;
}From the above source code (the part that does not involve numeric types has been deleted), we can see that (_count) calculates the new Entry[] size, so let's take a look at how the calculation logic of this new array size is implemented.
public static int ExpandPrime(int oldSize)
{
int newSize = 2 * oldSize;
if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize) return MaxPrimeArrayLength;
return GetPrime(newSize);
}For the expansion of the new entries array, first according to the original array size *2, then the maximum value that can be expanded is MaxPrimeArrayLength=0x7FFFFC3, corresponding to the maximum value of 32 bytes. When calculating the new array size, the corresponding minimum prime number will be multiplied by 2 times based on the original array, that is, realSize=2*oldSize*y (the minimum prime number in the prime number table).
[Note: In fact, in the entire C# expansion logic, most of the vast majority are expanded at 2 times (there are certain disadvantages in the 2 times expansion method. Assuming that the nth expansion allocates 2^n space (the constant C is omitted), then the total space released before is: 1 + 2 + 2^2 + ... + 2^(n-1) = 2^n - 1. The result is that the operating system needs to continuously allocate new memory pages, and the first address of the array is also increasing, resulting in cache missing.]
(_entries, entries, count) The expanded new array will perform Copy() operation on the old array. Every time the array is expanded in C#, all the elements of the array are copied into the new array. This process is time-consuming and resource-consuming. If the capacity of the array is calculated in advance during the actual development process, it can greatly improve performance and reduce the activity frequency of GC.
For the capacity initialized to set Dictionary, when the element is inserted for the first time, C# will initialize the two arrays, where size=3, that is, the minimum value in the maintained prime number table. After the array size exceeds the size, the capacity will be expanded according to the above expansion logic.
4. The implementation method of FindValue of Dictionary<TKey, TValue>
After introducing the element insertion of Dictionary<TKey, TValue>, let's take a look at the query logic of Dictionary<TKey, TValue>. The core method to implement query logic in Dictionary<TKey, TValue> is FindValue(). First, let's take a look at the source code of its implementation.
internal ref TValue FindValue(TKey key)
{
ref Entry entry = ref <Entry>();
if (_buckets != null)
{
uint hashCode = (uint)();
int i = GetBucket(hashCode);
Entry[]? entries = _entries;
uint collisionCount = 0;
i--;
do
{
if ((uint)i >= (uint))
{
goto ReturnNotFound;
}
entry = ref entries[i];
if ( == hashCode && EqualityComparer<TKey>.(, key))
{
goto ReturnFound;
}
i = ;
collisionCount++;
} while (collisionCount <= (uint));
goto ConcurrentOperation;
}
goto ReturnNotFound;
ConcurrentOperation:
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
ReturnFound:
ref TValue value = ref ;
Return:
return ref value;
ReturnNotFound:
value = ref <TValue>();
goto Return;
}In the above source code, the logic of calculating hashCode and calculating hash index will not be repeated. Focus on == hashCode &&(, key)). In FindValue(), the cached Entry[]? entries are cyclically traversed, and then compared in turn. The comparison logic contains two parts. When judging the value key, it is not only necessary to determine that the hashCode passed in the key value is equal to the hashCode value of the corresponding Entry[]? entries, but also to determine whether the key is the same. By comparing (, key), the logic about the comparator will be introduced in the next chapter.
5. Learn the final thoughts and insights
The above introduces some logics of initialization, element insertion, expansion of element insertion, and element value selection of Dictionary<TKey, TValue>. We can find that in Dictionary<TKey, TValue>, two arrays, nt[] buckets and Entry[]? _entries, are maintained in Dictionary<TKey, TValue>. The structure used to store data is Entry[]? _entries. This type is a structure. In C#, the memory occupied by the structure is less than the memory occupied by an object. No matter how complex the storage structure is, it will try to simplify it into an array as much as possible, and then optimize it through the storage and reading characteristics of the array, avoiding the shortcomings of the array in some aspects and giving full play to its advantages.
In the above part of the thinking, we can actually find several things to pay attention to in the actual coding process:
(1) When creating a storage structure, you need to think about its corresponding storage scenarios and objects, try to choose the appropriate structure for processing, and reduce memory usage.
(2) For the storage structure, try to specify the capacity in advance to avoid frequent expansion. Each expansion will be accompanied by the copying of the array.
(3) The C# expansion mechanism is based on the expansion of 2 times. In the hash storage structure, personalized calculation and optimization will be carried out according to the maintained prime number table.
(4) When interpreting the source code, you can first select a simple scenario, try to eliminate code that is unrelated to the scenario that needs to be verified, concentrate core logic for analysis, and then gradually expand thinking.
This is the end of this article about the detailed explanation of the storage structure of Dictionary<TKey,TValue> in C#. For more related contents of C#, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!