This article is a simple analysis of the internal implementation principle of Dictionary in c#. If there is any misrepresentation, please correct it.

The current version of the source code is. Net Framwork 4.8. Source address.

1. Key fields and Entry structure

        struct Entry
        {
            public int hashCode;    // key Of hashCode & 0x7FFFFFFF
            public int next;            // Point to the address of the next element in the list (actually entries The last element is-1
            public TKey key;
            public TValue value;
        }
        Entry[] entries;        //Storing key values
        int[] buckets;          //storage entries Index of the latest elements,Its storage location is determined by the result of the model taking. Example: Assume that key values are stored entries The position of the first element, and hashCode And the length of the model is 2, so buckets[2] = 1
        int count = 0;         //Number of stored key values
        int version;             //Record versions to prevent collection changes during iterations
        IEqualityComparer<TKey> _comparer;    
        int freeList;             //entries Index of the latest empty element
        int freeCount;         //entries Number of hollow elements

2. Add keys (Add)

        public void Add(TKey key, TValue value) {
            Insert(key, value, true);
        }


        private void Insert(TKey key, TValue value, bool add) {
        
            if( key == null ) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets == null) Initialize(0);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            //Take die
            int targetBucket = hashCode % buckets.Length;
#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode &&  comparer.Equals(entries[i].key, key)) {
                    if (add) {
                         ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    //For existing Key Reassign
                    entries[i].value = value;
                    version++;
                    return;
                }
#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }
            int index;
            if (freeCount > 0) {
                //existence entries Existence of empty elements
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else {
                if (count == entries.Length)
                {
                    //Expansion: greater than count * 2 Minimum prime number as entries and bucket New capacity (i.e. array length).Length)
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }
            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            //Index of header elements of access list (i.e. entries The last element stored in the enties Index in
            //Easy to take Key Each time you start traversing the header elements of the list, see FindEntry(TKey key)function
            buckets[targetBucket] = index;
            version++;
#if FEATURE_RANDOMIZED_STRING_HASHING
#if FEATURE_CORECLR
            // In case we hit the collision threshold we'll need to switch to the  comparer which is using randomized string hashing
            // in this case will be EqualityComparer<string>.Default.
            // Note, randomized string hashing is turned on by default on coreclr so  EqualityComparer<string>.Default will
            // be using randomized string hashing
            if (collisionCount > HashHelpers.HashCollisionThreshold && comparer ==  NonRandomizedStringEqualityComparer.Default)
            {
                comparer = (IEqualityComparer<TKey>)  EqualityComparer<string>.Default;
                Resize(entries.Length, true);
            }
#else
            if(collisionCount > HashHelpers.HashCollisionThreshold &&  HashHelpers.IsWellKnownEqualityComparer(comparer))
            {
                //If the number of collisions (single list length) is greater than the maximum collision threshold, it needs to be expanded.
                comparer = (IEqualityComparer<TKey>)  HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif // FEATURE_CORECLR
#endif
        }

******************************************************************************************************************************************
        static void Foo()
        {
            var dicData = new Dictionary<int, int>();
      //Add key value
            new List<int> { 1, 2, 4 }.ForEach(item => Add(item, dicData));
            new List<int> { 22, 29, 36, 20 }.ForEach(item => Add(item, dicData));
        }
        static void Add(int key, Dictionary<int, int> dicData)
        {
            dicData.Add(key, key);
        }

 

2.1 Array entries and buckets initialization

 

 

 

2.2 Add the key value {1,1}, then

    hashCode = 1;
  targetBucket = hasCode % buckets.Length;         //targetBucket = 1
    next = buckets[targetBucket];                               //next = -1
    buckets[targetBucket] = index;                             //buckets[1] = 0 

 

 

2.3 Add the key value {2,2}, then

    hashCode = 2;
  targetBucket = hasCode % buckets.Length;         //targetBucket = 2
    next = buckets[targetBucket];                               //next = -1
    buckets[targetBucket] = index;                              //buckets[2] = 1

 

 

2.4 Add the key value {4,4}, then

    hashCode = 4;
    targetBucket = hasCode % buckets.Length;         //targetBucket = 1
    next = buckets[targetBucket];                               //next = 0
    buckets[targetBucket] = index;                              //buckets[1] = 2

 

Next, the entries array is presented as a single linked list (i.e. the entries array is horizontal).

2.5 Before continuing to add key values, you need to expand the operation because entries are 3 in length and have elements. After expansion, Next of each element of buckets and entries needs to be reassigned.

            private void Resize(int newSize, bool forceNewHashCodes) {
            Contract.Assert(newSize >= entries.Length);
            //instantiation buckets,And set each element to-1
            int[] newBuckets = new int[newSize];
            for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
            Entry[] newEntries = new Entry[newSize];
            Array.Copy(entries, 0, newEntries, 0, count);
            //If it is Hash Collision Expansion, Use New HashCode Function recalculation Hash value
            if(forceNewHashCodes) {
                for (int i = 0; i < count; i++) {
                    if(newEntries[i].hashCode != -1) {
                        newEntries[i].hashCode =  (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
                    }
                }
            }
            //Reconstructing single linked list
            for (int i = 0; i < count; i++) {
                if (newEntries[i].hashCode >= 0) {
                    //Mould Resetting next Value sum buckets
                    int bucket = newEntries[i].hashCode % newSize;
                    newEntries[i].next = newBuckets[bucket];
                    newBuckets[bucket] = i;
                }
            }
            buckets = newBuckets;
            entries = newEntries;
        }

2.6 Continue to add key values {22,22}, {29,29}, {36,36}, {40,40} and the internal storage results are as follows.

3. Take the Key value (dic[22])

     public TValue this[TKey key] {
            get {
                //take Key Corresponding value entries Index of
                int i = FindEntry(key);
                if (i >= 0) return entries[i].value;
                ThrowHelper.ThrowKeyNotFoundException();
                return default(TValue);
            }
            set {
                //To update Key Corresponding value
                Insert(key, value, false);
            }
        }

    private int FindEntry(TKey key) {
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                //Traversing single linked list
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i =  entries[i].next) {
                    if (entries[i].hashCode == hashCode &&  comparer.Equals(entries[i].key, key)) return i;
                }
            }
            return -1;
        }
*********************************************************************************************
        static void Foo()
        {
            ......
            //take Key=22
            var val =dicData[22];

}

Simplify the code that takes the Key corresponding value

    var hashCode =comparer.GetHashCode(key) & 0x7FFFFFFF;   // 22
    var targetBuget = hashCode % buckets.Length;            //Modular operation 1  
    var i = bucket[targetBuget];                            //Index of header elements of linked list bucket[1] = 5
    //Traversing single linked list
    for (; i >= 0; i =  entries[i].next) {
        if (entries[i].hashCode == hashCode &&  comparer.Equals(entries[i].key, key)) return i;
    }

4. Remove key values

        public bool Remove(TKey key) {
            if(key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int last = -1;
                //The principle is to take out the key value first, and then record it. entries Free Index( freeList)And the number of free( freeCount)
                for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)  {
                    if (entries[i].hashCode == hashCode &&  comparer.Equals(entries[i].key, key)) {
                        if (last < 0) {
                            buckets[bucket] = entries[i].next;
                        }
                        else {
                            entries[last].next = entries[i].next;
                        }
                        entries[i].hashCode = -1;
                        //Establishing an idle list
                        entries[i].next = freeList;
                        entries[i].key = default(TKey);
                        entries[i].value = default(TValue);
                        //Preservation entryies Index of hollow elements
                        //When inserting a new key value, place it in the current index position and reduce it. entryies Waste of space
                        freeList = i;
                        //Number of empty elements plus 1
                        freeCount++;
                        version++;
                        return true;
                    }
                }
            }
            return false;
        }
*******************************************************************
        static void Foo()
        {
            ......
            //remove
            new List<int> { 22, 29 }.ForEach(item => dicData.Remove(item));
        } 

4.1 After removing Key=22, freeList = 3, freeCount = 1,

4.2 After removing Key=36, freeList = 5, freeCount = 2,

 

 

5. Insert the key value again

As shown above, when {36,36} is removed, a new linked list with two elements (the gray box in the figure above) is created. This function is to insert new key values into the entries array according to the index order of the "new linked list" records. Example: Add the key value {22,22}, {25,25}, and then freeList = 5, freeCount = 2;
  1. Assign entries[5], freeList = 3, freeCount = 1;
  2. Assign entries[3], freeList = 1, freeCount = 0;

 

Hopefully, this article will give you some insight into the internal implementation of Dictionary.